leetcode215 Kth Largest Element in an Array

 1 """
 2 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
 3 Example 1:
 4 Input: [3,2,1,5,6,4] and k = 2
 5 Output: 5
 6 Example 2:
 7 Input: [3,2,3,1,2,4,5,5,6] and k = 4
 8 Output: 4
 9 """
10 """
11 经典topK问题。好题
12 解法一：利用了快排思想。参考leetcode75解法二
13 解法二和三调用了python的heapq包。解法类似leetcode347解法二、三
14 后面可以尝试不调用包，自己写堆排序
15 """
16 class Solution1:
17     def findKthLargest(self, nums, k):
18         return self._find(nums, k-1, 0, len(nums)-1) #注意这里是k-1,第k大的在数组里是k-1
19     def _find(self, nums, k, l, r):
20         pivot = l
21         gt = l
22         i = l+1
23         lt = r+1
24         while i < lt:  #三路排序(由大到小)
25             if nums[i] > nums[pivot]:
26                 gt += 1
27                 nums[i], nums[gt] = nums[gt], nums[i]
28                 i += 1
29             elif nums[i] < nums[pivot]:
30                 lt -= 1
31                 nums[i], nums[lt] = nums[lt], nums[i]
32             else:
33                 i += 1
34         nums[pivot], nums[gt] = nums[gt], nums[pivot]
35         if gt >= k and gt > l:  #如果大于等于k,在左边[l, gt]
36             self._find(nums, k, l, gt)
37         if gt < k and gt+1 < r: #如果小于k,在右边[gt+1, r]
38             self._find(nums, k, gt+1, r)
39         return nums[k]
40 
41 """
42 解法二：将nums 中的每个-num存成堆结构
43 循环k，找到第k小的-num。即为第k大的num
44 """
45 class Solution2:
46     def findKthLargest(self, nums: List[int], k: int) -> int:
47         import heapq
48         heap = []
49         for num in nums:
50             heapq.heappush(heap, -num)
51         while k:
52             res = heapq.heappop(heap)
53             k -= 1
54         return -res
55 """
56 解法三：维护一个n-k的堆(有局限性,最大的值最后入堆,会出问题)
57 """
58 class Solution3:
59     def findKthLargest(self, nums, k):
60         import heapq
61         heap = []
62         res = []
63         for num in nums:
64             heapq.heappush(heap, -num)
65             if len(heap) > len(nums) - k:
66                 temp = heapq.heappop(heap)
67                 res.append(temp) #bug最开始没有这一行 Wrong answer
68               #Input
69               #[3,2,3,1,2,4,5,5,6]
70               #4
71               #Output
72               #6
73               #Expected
74               #4
75               #原因是最后进入堆中的num是最大的
76         return -max(res)
77 """
78 解法四：sorted函数，纯属娱乐
79 """
80 class Solution4:
81     def findKthLargest(self, nums: List[int], k: int) -> int:
82         return sorted(nums)[-k]
83 """
84 sorted函数说明:https://www.runoob.com/python/python-func-sorted.html
85 
86 sort 与 sorted 区别：
87 sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。
88 list 的 sort 方法返回的是对已经存在的列表进行操作，无返回值，
89 而内建函数 sorted 方法返回的是一个新的 list，而不是在原来的基础上进行的操作。
90 sorted(iterable, cmp=None, key=None, reverse=False)
91 iterable -- 可迭代对象。
92 cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
93 key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
94 reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。
95 """