Question
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.
Solution 1 -- PriorityQueue
1. 将所有元素放入heap中
2. 依次用poll()取出heap中最大值
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || k > nums.length)
return 0;
int length = nums.length, index = length - k, result = 0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(length,
new Comparator<Integer>(){
public int compare(Integer a, Integer b) {
return (a - b);
}
});
for (int i = 0; i < length; i++)
pq.add(nums[i]);
while (index >= 0) {
result = pq.poll();
index--;
}
return result;
}
}
Improvement
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || k > nums.length)
return 0;
int length = nums.length, index = k, result = 0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(length, Collections.reverseOrder());
for (int i = 0; i < length; i++)
pq.add(nums[i]);
while (index > 0) {
result = pq.poll();
index--;
}
return result;
}
}
Solution 2 -- Quick Select
Average Time O(n)
'''
a: [3, 2, 5, 1], 2
output: 2
''' def swap(a, index1, index2):
if index1 >= index2:
return
tmp = a[index1]
a[index1] = a[index2]
a[index2] = tmp def partition(a, start, end):
''' a[start:end]
pivot: a[end]
return: index of pivot
'''
pivot = a[end]
cur_big = start - 1
for i in range(start, end):
if a[i] >= pivot:
cur_big += 1
swap(a, cur_big, i)
cur_big += 1
swap(a, cur_big, end)
return cur_big def quick_select(a, k):
k -= 1
length = len(a)
start = 0
end = length - 1
while start < end:
index = partition(a, start, end)
if index == k:
return a[index]
if index > k:
# Note: end != index
end = index - 1
else:
# Note: start != index
start = index + 1
k = k - index
return -1 a = [3, 2, 5, 1]
k = 1
print(quick_select(a, k))