algorithms

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

kth-largest-element-in-an-arrayV1.cpp (1331B)

      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         while (i <= rightPos) {
     22             if (nums[i] >= pivotValue) {
     23                 swap(nums, i, rightPos);
     24                 rightPos--;
     25             } else {
     26                 swap(nums, i, leftPos);
     27                 leftPos++;
     28                 i++;
     29             }
     30         }        
     31         int pivotIndex = rightPos+1;
     32         swap(nums,pivotIndex,right);
     33 
     34         if(pivotIndex == k) {
     35             return nums[pivotIndex];
     36         }
     37         if(pivotIndex < k) {
     38             return quickSelect(nums,k,pivotIndex+1,right);
     39         }
     40         if(pivotIndex > k) {
     41             return quickSelect(nums,k,left,pivotIndex-1);
     42         }
     43         return -1;
     44 
     45     }
     46     int findKthLargest(vector<int>& nums, int k) {
     47         return quickSelect(nums,nums.size() - k,0,nums.size()-1);
     48     }
     49 };