Code & Func

第39天。

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

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

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

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

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

1
int heap_size;
2
inline int left(int idx) {
3
    return (idx << 1) + 1;
4
}
5
inline int right(int idx) {
6
    return (idx << 1) + 2;
7
}
8
void max_heapify(vector<int>& nums, int idx) {
9
    int largest = idx;
10
    int l = left(idx), r = right(idx);
11
    if (l < heap_size && nums[l] > nums[largest]) largest = l;
12
    if (r < heap_size && nums[r] > nums[largest]) largest = r;
13
    if (largest != idx) {
14
        swap(nums[idx], nums[largest]);
15
        max_heapify(nums, largest);
16 collapsed lines
16
    }
17
}
18
void build_max_heap(vector<int>& nums) {
19
    heap_size = nums.size();
20
    for (int i = (heap_size >> 1) - 1; i >= 0; i--)
21
        max_heapify(nums, i);
22
}
23
int findKthLargest(vector<int>& nums, int k) {
24
    build_max_heap(nums);
25
    for (int i = 0; i < k; i++) {
26
        swap(nums[0], nums[heap_size - 1]);
27
        heap_size--;
28
        max_heapify(nums, 0);
29
    }
30
    return nums[heap_size];
31
}

还有用STL中priority_queue的：

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