A Consise Divide and Conquer Solution


  • 1
    Z

    A Consise Divide and Conquer Solution, based on modifications of QuickSort Algorithm.

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            return Qsort_kth(nums, 0, nums.size() - 1, k - 1);
        }
        
    int Qsort_kth(vector<int> &nums, int l, int r, int k)
        {
            if (l < r){
                int x = nums[(l + r) / 2], i = l, j = r, t;
                while (i <= j)
                {
                    while (nums[i] > x) i++;
                    while (nums[j] < x) j--;
                    if (i <= j)
                    {
                        t = nums[i]; nums[i] = nums[j]; nums[j] = t;
                        i++; j--;
                    }
                }
                if (k <= j) return Qsort_kth(nums, l, j, k);
                else if (k >= i) return Qsort_kth(nums, i, r, k);
                else return nums[k];
            } else return nums[k];
        }
    };

  • 0
    public class solution {
            public int findKthLargest(int[] nums, int k) {
               return QsortKth(nums, 0, nums.size()-1,k-1);
         }
         private int QsortKth(int[] nums, int l, int r, int k) {
              if(l < r) {
                 int x = nums[(l + r) / 2];
                 int i = l, j = r, t;
                 while( i <= j) {
                      while( nums[i] > x)
                              i++;
                      while(nums[j] < x)
                              j--;
                       if(i <= j) {
                             t = nums[i];
                            nums[i] = nums[j];
                            nums[j] = t;
                            i++;
                            j--;
                         }
                       }
                     if(k <= j)
                       return QsortKth(nums, l, j, k);
                    else if(k >= i)
                       return QsortKth(nums, i, r, k);
                     else
                       return nums[k];
                  }
                  else
                     return nums[k];
    
    }
    
    
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.