O(n) C++ solution, quick select


  • 0
    A
    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
           return select(nums, 0, nums.size() - 1, nums.size() - k); 
        }
        
        int select(vector<int> &nums, int from, int to, int k) {
            if (from == to) return nums[from];
            int pivot = nums[from + (to - from) / 2];
            int l = from, r = to;
            while (l <= r) {
                while (nums[l] < pivot) l++;
                while (nums[r] > pivot) r--;
                if (l <= r) {
                    swap(nums[l], nums[r]);
                    l++; r--;
                }
            }
            if (k < l) return select(nums, from, l-1, k);
            return select(nums, l, to, k);
        }
    };
    

Log in to reply
 

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