【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素

2023-12-23 18:38:43

?《博主简介》

小伙伴们好，我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
?更多学习资源，可关注公-仲-hao:【阿旭算法与机器学习】，共同学习交流~
👍感谢小伙伴们点赞、关注！

《------往期经典推荐------》

一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】，已更新31期，欢迎关注，持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】

排序

翻转对

# 分治排序算法扩展

class?Solution:

????def?reversePairs(self,?nums:?List[int])?->?int:

????????def?merge(left,?right):

????????????# 统计前面比后面大的翻转对个数

????????????j =?0

????????????for?i in?range(len(left)):

????????????????while?j <?len(right)?and?left[i]?>?2?*?right[j]:

????????????????????j +=?1

????????????????self.count +=?j

????????????# 合并两个有序列表

????????????res =?[]

????????????while??len(left)?>?0?and?len(right)?>?0:

????????????????if?left[0]?<?right[0]:

????????????????????res.append(left.pop(0))

????????????????else:

????????????????????res.append(right.pop(0))

????????????if?left:

????????????????res.extend(left)

????????????if?right:

????????????????res.extend(right)

????????????return?res

????????def?mergeSort(arr):

????????????n =len(arr)

????????????if?n <?2:

????????????????return?arr

????????????middle =?n //?2

????????????left =?arr[:middle]

????????????right =?arr[middle:]

????????????sort_left =?mergeSort(left)

????????????sort_right =?mergeSort(right)

????????????return?merge(sort_left,?sort_right)

????????self.count =?0

????????mergeSort(nums)

????????return?self.count

股票问题

买卖股票的最佳时机

class?Solution:

????def?maxProfit(self,?prices:?List[int])?->?int:

????????if?not?prices:

????????????return?0

????????minValue =?prices[0]

????????res =?0

????????for?i in?range(1,?len(prices)):

????????????minValue =?min(minValue,?prices[i])

????????????res =?max(res,?prices[i]-minValue)

????????return?res

买卖股票的最佳时机3

TOP K问题

数组中的 第K个最大元素

class?Solution:

????def?findKthLargest(self,?nums:?List[int],?k:?int)?->?int:

????????# 使用快速排序

????????lo =?0

????????hi =?len(nums)?-?1

????????k =?len(nums)?-?k

????????while?lo <=?hi:

????????????p =?self.partition(nums,?lo,?hi)

????????????if?p >?k:

????????????????hi =?p -?1

????????????elif?p <?k:

????????????????lo =?p +?1

????????????else:

????????????????return?nums[p]

????????return?-1

????

????def??partition(self,?nums,?lo,?hi):

????????pivot =?nums[lo]

????????i =?lo

????????j =?hi

????????while?i <?j:

????????????while?i <?j and?nums[j]?>=?pivot:

????????????????j -=?1

????????????nums[i]?=?nums[j]

????????????while?i <?j and?nums[i]?<?pivot:

????????????????i +=?1

????????????nums[j]?=?nums[i]

????????nums[i]?=?pivot

????????return?i

数组中前K个最小的元素

def?partition(nums,?lo,?hi):

????pivot =?nums[lo]

????i =?lo

????j =?hi

????while?i <?j:

????????while?i <?j and?nums[j]?>=?pivot:

????????????j -=?1

????????nums[i]?=?nums[j]

????????while?i <?j and?nums[i]?<?pivot:

????????????i +=?1

????????nums[j]?=?nums[i]

????nums[i]?=?pivot

????return?i

def?getKminnums(nums,?k):

????index =?k -?1

????low =?0

????high =?len(nums)?-?1

????while?low <=?high:

????????p =?partition(nums,?low,?high)

????????if?p >?index:

????????????high =?p -?1

????????elif?p <?index:

????????????low =?p +?1

????????else:

????????????# 输出前k个元素

????????????return?nums[:index+1]

关于本篇文章大家有任何建议或意见，欢迎在评论区留言交流！

觉得不错的小伙伴，感谢点赞、关注加收藏哦！

欢迎关注下方GZH：阿旭算法与机器学习，共同学习交流~

文章来源:https://blog.csdn.net/qq_42589613/article/details/135171408
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。