Code & Fun

第39天。

今天的题目是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.

简单的做法就是先对无序的数组进行倒序排序,然后返回nums[k-1]即可。

1
2
3
4
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),[](int a,int b ){ return a > b; });
return nums[k-1];
}

时间复杂度是O(nlog(n)).然后是利用partition的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int findKthLargest(vector<int>& nums, int k) {
return findKthLargest(nums,0,nums.size() - 1,k-1);
}
int findKthLargest(vector<int> &nums,int first,int last,int k) {
int p = partition(nums,first,last);
if (k > p) return findKthLargest(nums,p+1,last,k);
else if (k < p) return findKthLargest(nums,first,p-1,k);
else return nums[p];
}
int partition(vector<int> &nums,int first,int last) {
if (first == last) return first;
swap(nums[first],nums[(random() % (last-first) + first)]);
int k = nums[first];
while(first < last) {
while(first < last && nums[last] <= k) last--;
nums[first] = nums[last];
while(first < last && nums[first] >= k) first++;
nums[last] = nums[first];
}
nums[first] = k;
return first;
}

显然和上面快排的方法一样时间复杂度都是O(nlogn).

然后是在dicuss中看到的用堆排的方法:

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
int heap_size;
inline int left(int idx) {
return (idx << 1) + 1;
}
inline int right(int idx) {
return (idx << 1) + 2;
}
void max_heapify(vector<int>& nums, int idx) {
int largest = idx;
int l = left(idx), r = right(idx);
if (l < heap_size && nums[l] > nums[largest]) largest = l;
if (r < heap_size && nums[r] > nums[largest]) largest = r;
if (largest != idx) {
swap(nums[idx], nums[largest]);
max_heapify(nums, largest);
}
}
void build_max_heap(vector<int>& nums) {
heap_size = nums.size();
for (int i = (heap_size >> 1) - 1; i >= 0; i--)
max_heapify(nums, i);
}
int findKthLargest(vector<int>& nums, int k) {
build_max_heap(nums);
for (int i = 0; i < k; i++) {
swap(nums[0], nums[heap_size - 1]);
heap_size--;
max_heapify(nums, 0);
}
return nums[heap_size];
}

还有用STLpriority_queue的:

1
2
3
4
5
6
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
for (int i = 0; i < k - 1; i++)
pq.pop();
return pq.top();
}

本文首发于Code & Fun