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.

My solution:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> nums_pq(nums.begin(), nums.end());
        for (int i=0; i<k-1; ++i) {
            nums_pq.pop();
        }
        return nums_pq.top();
    }
};

Runtime: 16 ms, faster than 83.56% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10.7 MB, less than 9.59% of C++ online submissions for Kth Largest Element in an Array.

复习了一下priority queue的用法：

• pq可以pop可以push，可以top输出当前最大。
• pq可以用指针初始化
• pq默认是less对比，所以左侧top就是最大
  • 如果要选最小，可以写priority_queue<int, vector<int>, greater<int>()> nums_pq(nums.begin(), nums.end());

改进版：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (k < nums.size()/2) {
            priority_queue<int> nums_pq(nums.begin(), nums.end());
            for (int i=0; i<k-1; ++i) {
                nums_pq.pop();
            }
            return nums_pq.top();
        }
        else {
            k = nums.size()-k+1; // 注意，这里是要+1，比如[3,2,1,5,6,4]第5大的是，第2小
            priority_queue<int, vector<int>, greater<int>> nums_pq(nums.begin(), nums.end());
            for (int i=0; i<k-1; ++i) {
                nums_pq.pop();
            }
            return nums_pq.top();
        }
    }
};

Runtime: 12 ms, faster than 95.49% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10.7 MB, less than 9.59% of C++ online submissions for Kth Largest Element in an Array.

拓展：pq和heap的区别

https://leetcode.com/problems/merge-k-sorted-lists/discuss/10527/difference-between-priority-queue-and-heap-and-c-implementation#:~:text=Priority%20queue%20is%20an%20abstract,to%20implement%20a%20priority%20queue.

https://www.geeksforgeeks.org/heap-using-stl-c/

https://www.fluentcpp.com/2018/03/13/heaps-priority-queues-stl-part-1/

Let’s consider the following heap (implemented as an array):

std::vector<double> numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

std::make_heap(begin(numbers), end(numbers));

// numbers is now {9, 8, 6, 7, 4, 5, 2, 0, 3, 1}

Removing the largest element
Finally, a priority queue needs to be able to remove its largest element with its pop method. The algorithm pop_heap moves the first element of the array to its end and rearranges the other elements into a heap:

std::pop_heap(begin(numbers), end(numbers)); // 9 is at the end
numbers.pop_back(); // 9 is gone, 8 is the new top

官方答案 O(N)

https://leetcode.com/problems/kth-largest-element-in-an-array/solution/

Approach 2: Quickselect

image.png

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def partition(left, right, pivot_index):
            pivot = nums[pivot_index]
            # 1. move pivot to end
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]  
            
            # 2. move all smaller elements to the left
            store_index = left
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[store_index], nums[i] = nums[i], nums[store_index]
                    store_index += 1

            # 3. move pivot to its final place
            nums[right], nums[store_index] = nums[store_index], nums[right]  
            
            return store_index
        
        def select(left, right, k_smallest):
            """
            Returns the k-th smallest element of list within left..right
            """
            if left == right:       # If the list contains only one element,
                return nums[left]   # return that element
            
            # select a random pivot_index between 
            pivot_index = random.randint(left, right)     
                            
            # find the pivot position in a sorted list   
            pivot_index = partition(left, right, pivot_index)
            
            # the pivot is in its final sorted position
            if k_smallest == pivot_index:
                 return nums[k_smallest]
            # go left
            elif k_smallest < pivot_index:
                return select(left, pivot_index - 1, k_smallest)
            # go right
            else:
                return select(pivot_index + 1, right, k_smallest)

        # kth largest is (n - k)th smallest 
        return select(0, len(nums) - 1, len(nums) - k)