Problem description:

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 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution priority_queue:

This problem can easily be solved by using STL container, priority queue.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # use min heap to store the largest K element
        # the top of the heap is Kth largest element because it's min heap
        pq = nums[:k]
        heapq.heapify(pq)
        
        for x in nums[k:]:
            heapq.heappush(pq, x)
            heapq.heappop(pq)
        return pq[0]
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end()); //put all elements in priority queue
        for (int i = 0; i < k - 1; i++) 
            pq.pop(); //remove the elements that is greater than Kth element
        return pq.top(); //Now the largest one is Kth 
    }
};

Solution quick sort:

However, this is not what this question is asking.
We can use quick sort to solve this question. The essential part of quick sort is sort the array by a pivot. The pivot will divide the array into two half, one half greater than pivot and the other smaller than pivot.

  1. Initialize left to be 0 and right to be nums.size() - 1;
  2. Partition the array, if the pivot is at the k-1-th position, return it (we are done);
  3. If the pivot is right to the k-1-th position, update right to be the left neighbor of the pivot;
  4. Else update left to be the right neighbor of the pivot.
  5. Repeat 2.
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
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums, left, r):
            # use l as pivot, partition nums to 
            # larger than nums[l] + equal to nums[l] + smaller than nums[l]
            pivot = nums[left]
            l = left+1
            while l <= r:
                if nums[l] < pivot and nums[r] > pivot:
                    nums[l], nums[r] = nums[r], nums[l]
                    l += 1
                    r -= 1
                if nums[l] >= pivot: # already greater, continue
                    l+= 1
                if nums[r] <= pivot: # already smaller, continue
                    r -= 1
            nums[left], nums[r] = nums[r], nums[left]
            return r
        l, r = 0, len(nums)-1
        while True:
            p = partition(nums, l, r)
            if p == k-1:
                return nums[p]
            elif p < k-1:
                l = p+1
            else:
                r = p-1
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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //quick sort: find a pivot and partition the list into two half. greater than pivot and smaller than pivot
        //if pivot is k-1th, then return
        int left= 0, right= nums.size()-1;
        while(1){
            int p= sort(nums, left, right);
            if(p == k-1)
                return nums[p];
            if(p < k-1)
                left= p+1;
            else
                right= p-1;
        }
    }
    
    int sort(vector<int>& nums, int left, int right){
        //use left most element as pivot, greater than pivot put left side.
        int pivot= nums[left]; 
        int l= left+1, r= right;
        while(l<= r){
            if(nums[l]< pivot && nums[r] > pivot)
                swap(nums[l++], nums[r--]);
            if(nums[l]>= pivot)
                l++;
            if(nums[r]<= pivot)
                r--;
        }
        //the nums[r] is greater than nums[left], so need to swap 
        swap(nums[left], nums[r]);
        return r;
    }
};

time complexity: $O(nlogn)$
space complexity: $O(1)$

reference:
https://goo.gl/R5oX7C