Kth Largest Element in an Array

#leetcode #algorithms #array

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

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

Approach #1: Sort the array and get by index

Time complexity is O(NlogN), a flaw is we modified the original array.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

Approach #2: Use heak minheap with size K

If we initialize a minheap with the size of K, the top value is what we want.

For minheap, the insertion operation has a worst-case time complexity of O(logN) but an average-case complexity of O(1).

So we have an overall average-case complexity of O(N) and worst time complexity O(NlogN).

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minheap;
        for(int i=0; i<k; i++)
            minheap.push(nums[i]);
        for(int i=k; i<nums.size(); i++){
            if(nums[i] <= minheap.top()) continue;
            minheap.pop();
            minheap.push(nums[i]);
        }
        return minheap.top();
    }
};

Approach #3: Divide and conquer

Just like quicksort, we use a partition function to split the array into two parts, the left part of elements are all less than pivot, the right part of elements are all greater than pivot.

And reduce the search range in every iteration.

The overall time complexity O(N).

class Solution {

private:
  void swap(vector<int>& a, int x, int y) {
    int t = a[y];
    a[y] = a[x];
    a[x] = t;
  }

  int random(int a, int b) {
    return (int) (rand() % (b - a + 1)) + a;
  }

  int partition(vector<int>& nums, int left, int right, int index) {
    int pivot = nums[index];
    swap(nums, index, right);
    int i = left - 1;
    for (int j=left; j<=right-1; j++)
      if (nums[j] <= pivot)
        swap(nums, ++i, j);
    swap(nums, right, i+1);
    return i+1;
  }

  int quick_select(vector<int>& nums, int left, int right, int k) {
    while (left <= right) {
      int pivot = partition(nums, left, right, random(left, right));
      if (pivot == k) return nums[k];
      else if (k > pivot) left = pivot + 1;
      else right = pivot - 1;
    }
    return -1;
  }

public:
  int findKthLargest(vector<int>& nums, int k) {
    return quick_select(nums, 0, nums.size() - 1, nums.size() - k);
  }
};