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.
Example
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
Solution
- Sort: O(nlogn)
- Quick Select: O(n)
(Kth-Largest-Element-in-an-Array.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| import random
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
pivot = random.choice(nums)
# 放比pivot大的num
nums1 = []
# 放比pivot小的num
nums2 = []
for num in nums:
if num > pivot:
nums1.append(num)
if num < pivot:
nums2.append(num)
# 答案在num1中
if k <= len(nums1):
return self.findKthLargest(nums1,k)
# 答案在num2中，不等式右边表示和pivot相等的nums数加len(nums1)
if k > len(nums) - len(nums2):
return self.findKthLargest(nums2,k-(len(nums)-len(nums2)))
# 若k<=len(nums)-len(nums2)说明,第k大不在num1中，他和pivort相等
return pivot
|