algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

kth-largest-element-in-an-arrayV2.cpp (1485B)

      1 class Solution {
      2 public:
      3     void swap(vector<int>& nums, int p1, int p2) {
      4         int temp = nums[p1];
      5         nums[p1] = nums[p2];
      6         nums[p2] = temp;
      7         return;
      8     }
      9     int quickSelect(vector<int>& nums, int k, int left, int right) { 
     10         int rightPos = right;
     11         int rndPos = right;
     12         if(right - left > 0) {
     13             rndPos = rand() % (right - left) + left;
     14         }
     15         int leftPos = left;
     16         int pivotValue = nums[rndPos];
     17         swap(nums,right,rndPos);
     18         rightPos -= 1;
     19         int i = left;
     20 
     21         int matchCount = 0;
     22 
     23         while (i <= rightPos) {
     24             if (nums[i] >= pivotValue) {
     25                 if (pivotValue == nums[i]) {
     26                     matchCount += 1;
     27                 }
     28                 swap(nums, i, rightPos);
     29                 rightPos--;
     30             } else {
     31                 swap(nums, i, leftPos);
     32                 leftPos++;
     33                 i++;
     34             }
     35         }
     36 
     37         int pivotIndex = rightPos+1;
     38         swap(nums,pivotIndex,right);
     39 
     40         if(pivotIndex + matchCount >= k && pivotIndex <= k) {
     41             return nums[pivotIndex];
     42         }
     43         if(pivotIndex < k) {
     44             return quickSelect(nums,k,pivotIndex+1,right);
     45         }
     46         if(pivotIndex > k) {
     47             return quickSelect(nums,k,left,pivotIndex-1);
     48         }
     49         return -1;
     50 
     51     }
     52     int findKthLargest(vector<int>& nums, int k) {
     53         return quickSelect(nums,nums.size() - k,0,nums.size()-1);
     54     }
     55 };