215. Kth Largest Element in an Array - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        low, high = 0, len(nums)-1
        while low <= high:
            pivot_idx = random.randint(low, high) # not sorted so not use middle 
            partition_idx = self.partition(nums, low, high, pivot_idx)
            if partition_idx == k - 1:
                return nums[partition_idx]
            elif partition_idx < k - 1:
                low = partition_idx + 1
            else:
                high = partition_idx - 1        
        return nums[k-1]
    
    # partition nums[low: high+1] such that nums[low: idx] > nums[idx] > nums[idx+1: high+1] 
    # in other words, nums[idx] is the idx+1-th largest
    def partition(self, nums: List[int], low: int, high: int, pivot_idx: int) -> int:
        # using nums[high]: working but might fall into worst case
        # using nums[idx]: working and likely to avoid worst case
        pivot = nums[pivot_idx]
        nums[pivot_idx], nums[high] = nums[high], nums[pivot_idx]
        
        
        partition_idx = low
        for i in range(low, high): # skip nums[high] intentionally
            if nums[i] > pivot:
                nums[partition_idx], nums[i] = nums[i], nums[partition_idx]
                partition_idx += 1
        nums[partition_idx], nums[high] = nums[high], nums[partition_idx]
        return partition_idx

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        shuffle(nums);
        int sz = nums.size(), low = 0, high = sz - 1;
        while (low <= high) { // low < high doesn't matter
            int p = partition(nums, low, high);
            if (p == k - 1) { // attention k - 1, not k
                return nums[p];
            } else if (p < k - 1) {
                low = p + 1; //attention p + 1 not p
            } else { // p > k
                high = p - 1; //attention p - 1 not p
            }
        }
        return nums[k - 1];
    }
private:
    void shuffle(vector<int>& nums) {
        int sz = nums.size();
        for (int i = sz - 1; i > 0; i--) {
            int j = rand() % (i + 1); // [0, i]
            swap(nums[i], nums[j]);
        }
    }
    
    int partition(vector<int>& nums, int low, int high) {
    /*  an valid implementation
        int pivot = nums[high], i = low;
        for (int j = low; j < high; j++) {
            if (nums[j] > pivot) {
                swap(nums[i++], nums[j]);
            }
        }
        swap(nums[i], nums[high]);
        return i;
    */
        int pivot = nums[low];
        int start = low + 1, end = high;
        while (start <= end) { 
            if (nums[start] > pivot) {
                start++;
            } else if (nums[end] <= pivot) {
                end--;
            } else {
                swap(nums[start++], nums[end--]);
            }
        }
        /* a buggy implementation
        swap(nums[low], nums[start]); //start is not guaranteed valid
        return start;
        */
        swap(nums[low], nums[end]);
        return end;
    }
};

int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (int i = 0; i < nums.size(); i++) {
            pq.push(-nums[i]);
            if (pq.size() > k) { //pop less than kth largest => min heap
                pq.pop();
            }
        }
        return -pq.top();
    }