Quick sort styled C++


  • 1
    C
    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            return findK(nums, 0, nums.size() - 1, k);
        }
        int findK(vector<int> &nums, int st, int ed, int k) {
            //cout << "call" << st << " " << ed << " " << k << endl;
            if (st >= ed) return nums[st];
            int i = st, j = ed, tmp;
            int x = nums[i];
            while (i <= j) {
                while (nums[i] < x) i++;
                while (nums[j] > x) j--;
                if (i <= j) {
                    tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
                    i++; j--;
                }
            }
            if (ed - i + 1 >= k) return findK(nums, i, ed, k);
            if (ed - j < k) return findK(nums, st, j, k - (ed - j));
            return nums[j + 1]; //In this case, there could only be one number between i and j
        }
    };

  • 0
    N
    This post is deleted!

Log in to reply
 

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