DEV Community is a community of 786,090 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

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

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