215. 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.

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.

// HeapSort
// Repeatedly remove the largest element from the heap (the root of the heap), and insert it into the array.
// Heapify procedure can be applied to a node if its children nodes are heapified.
void heapify(vector<int>& nums, int heap_size, int i) { // time: O(nlogn); space: O(1)
    int largest = i;
    int left = 2 * largest + 1, right = 2 * largest + 2;
    if (left < heap_size && nums[left] > nums[largest]) largest = left;
    if (right < heap_size && nums[right] > nums[largest]) largest = right;
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, heap_size, largest); // tail recursion
    }
}
int findKthLargest(vector<int>& nums, int k) {
    int heap_size = nums.size();
    for (int i = heap_size / 2 - 1; i >= 0; --i) {
        heapify(nums, heap_size, i);
    }
    for (int i = 0; i < k; ++i) {
        swap(nums[0], nums[heap_size - 1]);
        --heap_size;
        heapify(nums, heap_size, 0);
    }
    return nums[heap_size];
}

// STL sort
int findKthLargest(vector<int>& nums, int k) { // time: O(nlogn); space: O(1)
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}

// Priority_queue
int findKthLargest(vector<int>& nums, int k) { // time: O(nlogk); space: O(k)
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < nums.size(); ++i) {
        pq.push(nums[i]);
        if (pq.size() > k) pq.pop();
    }
    return pq.top();
}

// Similar QuickSort
int partition(vector<int>& nums, int left, int right) { // time: O(n) for average, O(n^2) for the worst; space: O(1)
    int pivot = nums[left], l = left + 1, r = right;
    while (l <= r) {
        if (nums[l] < pivot && nums[r] > pivot) {
            swap(nums[l++], nums[r--]);
        }
        while (l <= r && nums[l] >= pivot) ++l;
        while (l <= r && nums[r] <= pivot) --r;
    }
    swap(nums[left], nums[r]);
    return r;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot_idx = partition(nums, left, right);
        if (pivot_idx == k - 1) return nums[k - 1];
        else if (pivot_idx < k - 1) left = pivot_idx + 1;
        else right = pivot_idx - 1;
    }
}

// QuickSelect (Randomly choose a pivot)
int partition(vector<int>& nums, int left, int right, int pivot_index) { // time: O(n) for average, O(n^2) for the worst; space: O(1)
    int pivot = nums[pivot_index];
    swap(nums[pivot_index], nums[right]);
    int p_index = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] >= pivot) {
            swap(nums[p_index++], nums[i]);
        }
    }
    swap(nums[p_index], nums[right]);
    return p_index;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot_index = left + rand() % (right - left + 1);
        pivot_index = partition(nums, left, right, pivot_index);
        if (pivot_index == k - 1) return nums[k - 1];
        else if (k - 1 < pivot_index) right = pivot_index - 1;
        else left = pivot_index + 1;
    }
}

// QuickSelect (Choose the right one as a pivot)
int partition(vector<int>& nums, int left, int right) { // time: O(n) for average, O(n^2) for the worst; space: O(1)
    int pivot = nums[right], p_index = left;
    for (int i = left; i < right; ++i) {
        if (nums[i] >= pivot) {
            swap(nums[p_index++], nums[i]);
        }
    }
    swap(nums[p_index], nums[right]);
    return p_index;
}
int findKthLargest(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while (true) {
        int pivot_index = partition(nums, left, right);
        if (pivot_index == k - 1) return nums[k - 1];
        else if (k - 1 < pivot_index) right = pivot_index - 1;
        else left = pivot_index + 1;
    }
}