Quick Select

code 2

key point: 1) use partition to divide the vector; 2) figure out left part or right part to conitnue;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0)
        {
            return 0;
        }

        return helper(nums, k, 0, n-1);
    }

    int helper(vector<int>& nums, int k, int s, int e)
    {
        if(s == e)
        {
            return nums[s];
        }

        int pos = partition(nums, k, s, e);
        if(pos + 1 == k)
        {
            return nums[pos];
        }
        else if(pos + 1 < k)
        {
            return helper(nums, k, pos+1, e);
        }
        else
        {
            return helper(nums, k, s, pos-1);
        }

    }

    int partition(vector<int>& nums, int k, int s, int e)
    {
        int l = s;
        int r = e;
        int pivot = nums[s];

        while(l < r)
        {
            while(l<r && nums[r] <= pivot)
            {
                r--;
            }
            nums[l] = nums[r];

            while(l<r && nums[l] >= pivot)
            {
                l++;
            }
            nums[r] = nums[l];
        }

        nums[l] = pivot;
        return l;
    }
};

code

class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        // write your code here
        if(nums.size() == 0)
        {
            return 0;
        }

        return qselect(nums, k, 0, nums.size()-1);
    }

    int qselect(vector<int>& nums, int k, int s, int e)
    {
        if(s >= e)
        {
            return nums[s];
        }

        int pos = partition(nums, k, s, e);
        if(pos + 1 == k)
        {
            return nums[pos];
        }
        else if(pos + 1 < k)
        {
            return qselect(nums, k, pos+1, e);
        }
        else
        {
            return qselect(nums, k, s, pos-1);
        }
    }

    int partition(vector<int>& nums, int k, int s, int e)
    {
        int pivot = nums[s];
        int l = s;
        int r = e;

        while(l < r)
        {
            while(l < r && nums[r] <= pivot)
            {
                r--;
            }
            nums[l] = nums[r];

            while(l < r && nums[l] >= pivot)
            {
                l++;
            }
            nums[r] = nums[l];
        }

        nums[l] = pivot;
        return l;
    }
};