4ms 13-line Non-Recusive Implementation of QuickSelect


  • 0

    The signiture of nth_element is fully compatible with C++ STL function nth_element.

    In the function, I use partition.

    class Solution {
    public:
    	int findKthLargest(vector<int>& nums, int k) {
    		vector<int>::iterator mid = prev(nums.end(), k);
    		nth_element(nums.begin(), mid, nums.end());
    		return *mid;
    	}
    protected:
    	template<typename RanIt>
    	void nth_element(RanIt first, RanIt nth, RanIt last)
    	{
    		for (; distance(first, last) > 1;)
    		{
    			auto pivot = *first;
    			RanIt pfirst = partition(first, last,
    				[pivot](int x){ return x < pivot;  });
    			RanIt plast = partition(pfirst, last,
    				[pivot](int x){ return !(pivot < x); });
    
    			if (nth < pfirst)
    			{
    				last = pfirst;
    			}
    			else if (nth < plast)
    			{
    				break;
    			}
    			else
    			{
    				first = plast;
    			}
    		}
    		return;
    	}
    };

Log in to reply
 

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