C++ Quick Sort like solution.


  • 0
    E
    class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k)
    {
    	return findKth(nums, 0, nums.size() - 1, k);
    }
    private:
    int findKth(std::vector<int> v, int start, int end, int k)
    {
    	int i = start;
    	int j  = end;
    	int baseVal = v[start];
    	int temp;
    
    	while (i < j)
    	{
    
    		while (v[j] > baseVal && i < j)
    			j--;
    
    		while (v[i] <= baseVal && i < j)
    			i++;
    
    		if (i >= j)
    			break;
    		temp = v[i];
    		v[i] = v[j];
    		v[j] = temp;
    	}
    
    	v[start] = v[i];
    	v[i] = baseVal;
    
    	if (k < (end - i + 1))
    		return findKth(v, i + 1, end, k);
    	else if (k > (end - i + 1))
    		return findKth(v, start, i - 1, k - (end - i + 1));
    	else
    		return v[end - (k - 1)];
    }
    };

Log in to reply
 

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