16ms C++ solution using partition


  • 1
    Q
    class Solution {
        // this function tries to find the proper pivot by comparing 3 elements in the vector
        // which helps improve the efficiency
        void handlePivot(vector<int>& nums, int left, int right) {
            int mid = (left + right) / 2;
            if (mid == left) return;
            if (nums[left] > nums[mid] && nums[left] > nums[right]) {
                if (nums[mid] > nums[right]) swap(nums[left], nums[mid]);
                else swap(nums[left], nums[right]);
            }
            else if (nums[left] < nums[mid] && nums[mid] > nums[right]) {
                if (nums[left] < nums[right]) swap(nums[left], nums[right]);
            }
            else {
                if (nums[left] < nums[mid]) swap(nums[left], nums[mid]);
            }
        }
    	int partition(vector<int>& nums, int left, int right) {
    		if (left == right) return left;
    		int l = left + 1, r = right;
    		handlePivot(nums, left, right);
    		int pivot = nums[left];
    		while (true) {
    			while (l <= r && nums[l] >= pivot) ++l;
    			while (nums[r] < pivot && r >= l) --r;
    			if (l >= r) break;
    			swap(nums[l++], nums[r--]);
    		}
    		swap(nums[left], nums[l - 1]);
    		return l - 1;
    	}
    public:
    	int findKthLargest(vector<int>& nums, int k) {
    		if (k > nums.size() || k <= 0 || nums.size() == 0) return 0;
    		int left = 0, right = nums.size() - 1;
    		while (left <= right) {
    			int pos = partition(nums, left, right);
    			if (pos == k - 1) return nums[pos];
    			if (pos < k - 1) left = pos + 1;
    			else right = pos - 1;
    		}
    		return nums[left];
    	}
    };
    

Log in to reply
 

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