LeetCode 215. Kth Largest Element in an Array

题目

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.

For 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.

分析

返回数组中的第 k 大元素

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution(object):
# O(n) time, quick selection
def findKthLargest(self, nums, k):
# convert the kth largest to smallest
return self.findKthSmallest(nums, len(nums)+1-k)
def findKthSmallest(self, nums, k):
if nums:
pos = self.partition(nums, 0, len(nums)-1)
if k > pos+1:
return self.findKthSmallest(nums[pos+1:], k-pos-1)
elif k < pos+1:
return self.findKthSmallest(nums[:pos], k)
else:
return nums[pos]
# choose the right-most element as pivot
def partition(self, nums, l, r):
low = l
while l < r:
if nums[l] < nums[r]:
nums[l], nums[low] = nums[low], nums[l]
low += 1
l += 1
nums[low], nums[r] = nums[r], nums[low]
return low
# O(nlgn) time
def findKthLargest1(self, nums, k):
return sorted(nums, reverse=True)[k-1]
# O(nk) time, bubble sort idea, TLE
def findKthLargest2(self, nums, k):
for i in xrange(k):
for j in xrange(len(nums)-i-1):
if nums[j] > nums[j+1]:
# exchange elements, time consuming
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums[len(nums)-k]
# O(nk) time, selection sort idea
def findKthLargest3(self, nums, k):
for i in xrange(len(nums), len(nums)-k, -1):
tmp = 0
for j in xrange(i):
if nums[j] > nums[tmp]:
tmp = j
nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
return nums[len(nums)-k]
# O(k+(n-k)lgk) time, min-heap
def findKthLargest4(self, nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
for _ in xrange(len(nums)-k):
heapq.heappop(heap)
return heapq.heappop(heap)
# O(k+(n-k)lgk) time, min-heap
def findKthLargest5(self, nums, k):
return heapq.nlargest(k, nums)[k-1]

点评

快排?堆排序????