2 C++ Solutions using STL partition and nth_element


  • 0
    X

    Quick Select

    class Solution {
    public:
    	int findKthLargest(vector<int>& nums, int k) {
    		auto left = nums.begin(), right = nums.end();
    		while (true) {
    			auto pivot = *next(left, distance(left, right) / 2);
    			auto mid1 = partition(left, right, 
                                                [&pivot](int& em) {return em > pivot; });
    			auto mid2 = partition(mid1, right, 
                                               [&pivot](int& em) {return em == pivot; });
    			int idx = distance(nums.begin(), mid1) + 1;
    			if (idx == k)return *mid1;
    			if (idx> k) right = mid1;
    			else left = next(mid1);
    		}
    	}
    };
    

    And nth_element 9ms

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            nth_element(nums.begin(),nums.begin()+k-1,nums.end(),
                                 std::greater<int>());
            return nums[k-1];
        }
    };
    

Log in to reply
 

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