Advertisement
HjHimansh

Kth Maximum - HJ

Sep 1st, 2020
1,071
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     int k;
  3.     public:
  4.  
  5.         int q_partition(vector<int> & nums, int k, int l, int r_pivot) {
  6.             int pivot = nums[r_pivot];
  7.             int i = k;
  8.             int j = k;
  9.             int z = l;
  10.  
  11.             while (i <= l && j <= z) {
  12.                 bool enteredBelowLoop = false;
  13.                 while (nums[j] == pivot && z>=0 && j <= z) {
  14.                     swap(nums[j], nums[z]);
  15.                     z--;
  16.                     enteredBelowLoop = true;
  17.                 }
  18.                
  19.                 if(enteredBelowLoop){
  20.                     continue;
  21.                 }
  22.                 if (nums[j] < pivot) {
  23.                     swap(nums[i], nums[j]);
  24.                     i++;
  25.                     j++;
  26.                 } else {
  27.                     j++;
  28.                 }
  29.             }
  30.  
  31.             int to_return = -1;
  32.             //now my j points to the position I can start putting my pivot at
  33.             z++;
  34.             while (z <= l) {
  35.                 swap(nums[i], nums[z]);
  36.                 if (to_return == -1) to_return = i;
  37.                 i++;
  38.                 z++;
  39.             }
  40.  
  41.             return to_return;
  42.         }
  43.  
  44.     int quickSort(vector < int > & nums, int i, int j) {
  45.         int r_pivot = i + (rand() % (j - i + 1));
  46.         int pIndex = q_partition(nums, i, j, r_pivot);
  47.         if (pIndex == nums.size() - k) {
  48.             return nums[pIndex];
  49.         }
  50.         if (pIndex < nums.size() - k) {
  51.             return quickSort(nums, pIndex + 1, j);
  52.         }
  53.         return quickSort(nums, i, pIndex - 1);
  54.     }
  55.  
  56.     int findKthLargest(vector < int > & nums, int tempK) {
  57.         k = tempK;                    
  58.         return quickSort(nums, 0, nums.size() - 1);
  59.        
  60.     }
  61. };
Advertisement
RAW Paste Data Copied
Advertisement