分治算法【三】——应用：Leetcode215. 数组中的第K个最大元素

题目：数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

这里主要是以分治算法来求解这道题，关于分治算法的思路，可以click here, 有关很多的其它解法可看leetcode官方解法

1、 要解决什么？

求解数组中第K个最大值。

2、如何使用分治算法去解决？

首先，我们应该先将这题转换为利用分治算法去解决排序问题，按从大到小排序，然后取出排序后的第k个值即可。

3、分治排序模板？

def Merge_Sort(lists): if len(lists) <=1 : return lists mid = len(lists) // 2 left = Merge_Sort(lists[:mid]) #将列表从中间分为两部分 right = Merge_Sort(lists[mid:]) return Merge(left, right) #合并两个列表 def Merge(left,right): r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] > right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += left[l:] result += right[r:] return result

这道题完整代码：

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def Merge_Sort(lists): if len(lists) <=1 : return lists mid = len(lists) // 2 left = Merge_Sort(lists[:mid]) #将列表从中间分为两部分 right = Merge_Sort(lists[mid:]) return Merge(left, right) #合并两个列表 def Merge(left,right): r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] > right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += left[l:] result += right[r:] return result a = Merge_Sort(nums) # print(a) return a[k-1]