Interesting algorithms

215. Kth Largest Element in an Array

Kth Largest Element in an Array - LeetCode

We can have

O(nlogn), O(nlogk) and O(n) complexity for this problem.

It is very interesting.

O(nlogn) is very trival. O(nlogk) can be foud here.

this is fast, it takes only 12 ms.

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

We can also use the STL partial_sort

something between [start, end) will be sorted.

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

O(n)

quick select. A naive implementation is super slow as below

runtime 224ms.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int pivot = nums[0];
        vector<int> left, right;
        for(int i=1;i<nums.size();++i){
            if(nums[i]>pivot)left.push_back(nums[i]);
            else right.push_back(nums[i]);
        }
        const int l= left.size(), r= right.size();
        if(l>=k) return findKthLargest(left, k);
        else if(l==k-1) return pivot;
        else return findKthLargest(right, k-l-1);
    }
};

Offical solution is about 12 ms

class Solution {
public:
    
  int partition(vector<int>& nums,int left, int right, int pivot_index) {
    int pivot = nums[pivot_index];
    // 1. move pivot to end
    swap(nums[pivot_index], nums[right]);
    int store_index = left;
// 2. move all smaller elements to the left
    for (int i = left; i <= right; i++) {
      if (nums[i] < pivot) {
        swap(nums[store_index], nums[i]);
        store_index++;
      }
    }
// 3. move pivot to its final place
    swap(nums[store_index], nums[right]);
return store_index;
  }
int quickselect(vector<int>&nums,int left, int right, int k_smallest) {
    /*
    Returns the k-th smallest element of list within left..right.
    */
if (left == right) // If the list contains only one element,
      return nums[left];  // return that element
// select a random pivot_index
    int pivot_index = left + rand()%(right - left+1); 
    
    pivot_index = partition(nums, left, right, pivot_index);
// the pivot is on (N - k)th smallest position
    if (k_smallest == pivot_index)
      return nums[k_smallest];
    // go left side
    else if (k_smallest < pivot_index)
      return quickselect(nums, left, pivot_index - 1, k_smallest);
    // go right side
    return quickselect(nums, pivot_index + 1, right, k_smallest);
  }
    
    int findKthLargest(vector<int>& nums, int k) {
        return quickselect(nums, 0, nums.size() - 1, nums.size() - k);
    }
};

System builtin nth_element

only 8ms.

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