DEV Community

Nic
Nic

Posted on • Originally published at coderscat.com on

Kth Largest Element in an 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
Enter fullscreen mode Exit fullscreen mode

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];
    }
};

Enter fullscreen mode Exit fullscreen mode

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();
    }
};

Enter fullscreen mode Exit fullscreen mode

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);
  }
};

Enter fullscreen mode Exit fullscreen mode

The post Kth Largest Element in an Array appeared first on Coder's Cat.

Discussion (0)