C++ 4ms solution, based on quick sort


  • 0
    H
    class Solution
    {	int divideVector(int* nums, int count){
    		
    		int pivot = nums[0];
    		int splitPosition = 0;
    		for (int n = 1; n < count; ++n){
    			if (nums[n] > pivot){
    				int temp = nums[splitPosition];
    				nums[splitPosition] = nums[n];
    				nums[n] = temp;
    				++splitPosition;
    			}
    		}
    		return splitPosition;
    	}
    
    	int largest(int * nums, int count){
    		int largestValue = nums[0];
    		for (int n = 1; n < count; ++n){
    			if (nums[n] > largestValue){
    				largestValue = nums[n];
    			}
    		}
    		return largestValue;
    	}
    
    	int smallest(int * nums, int count){
    		int smallestValue = nums[0];
    		for (int n = 1; n < count; ++n){
    			if (nums[n] < smallestValue){
    				smallestValue = nums[n];
    			}
    		}
    		return smallestValue;
    	}
    
    	int recursiveFindKthLargest(int * nums, int count, int k){
    		if (k == 1){
    			return largest(nums, count);
    		}
    
    		int splitCount = divideVector(nums, count);
    
    		if (splitCount == 0){
    			return recursiveFindKthLargest(nums + 1, count - 1, k - 1);
    		}
    		else{
    			if (splitCount > k){
    				return recursiveFindKthLargest(nums, splitCount, k);
    			}
    			else if (splitCount < k){
    				return recursiveFindKthLargest(nums + splitCount, count - splitCount, k - splitCount);
    			}
    			else
    				return smallest(nums, splitCount);
    		}
    	}
    
    	int findKthLargest(vector<int>& nums, int k) {
    		return recursiveFindKthLargest(&nums[0], nums.size(), k);
    	}
    }

  • 0
    C
    class Solution {
    public:
        int split(vector<int>& nums, int start, int end) {
        	int temp = nums[end];
        	int i = start - 1;
        	for (int j = start; j < end; j++) {
        		if (nums[j] > temp) {
        			i++;
        			swap(nums[i], nums[j]);
        		}
        	}
        	swap(nums[i+1], nums[end]);
        	return i+1;
        }
        
        int help(vector<int>& nums, int start, int end, int k) {
        	int r = split(nums, start, end);
        	if ((r - start + 1) == k) {
        		return nums[r];
        	}
        	else if ((r - start + 1) > k) {
        		return help(nums, start, r - 1, k);
        	}
        	else {
        		return help(nums, r + 1, end, k - r + start - 1);
        	}
        }
        
        int findKthLargest(vector<int>& nums, int k) {
            return help(nums, 0, nums.size() - 1, k);
        }
    };

Log in to reply
 

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