Divide and conquer with C++


  • 0
    S
    class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
        return findKth(nums, 0, nums.size() - 1, k);
    }
    
    int findKth(vector<int>& nums, int l, int r, int k) {
        int pivot = nums[l];
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && nums[j] <= pivot) {
                --j;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] >= pivot) {
                ++i;
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        if (i == k - 1) {
            return nums[i];
        } else if (i > k - 1) {
            return findKth(nums, 0, i - 1, k);
        } else {
            return findKth(nums, i + 1, nums.size() - 1, k);
        }
    }
    };

Log in to reply
 

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