my 1ms Java solution beats 100%...


  • 9
    X

    The idea is to use modified quick sort. We know the key point of quick sort is to divide the array into two parts, one is smaller than(or equal to) the pivot value, and the other half bigger than it(or equal).

    The modified version is we only sort the part if the kth element is within it. Let's say we know the kth biggest element should appear at the index array[n-k] (where n is the size), and each time when we divide the array into two parts by using the pivot value, we check the range of each part, if index [n-k] is not within the range we won't sort it.

    And to increase the chance of dividing the array into two parts of equal length I choose the pivot which is the median among start, end and mid element.

    public class Solution {
    public int findKthLargest(int[] nums, int k) {
    int n = nums.length;
    int target = n - k;
    quicksort(nums, 0, n-1, target);
    return nums[n-k];
    }

    private void quicksort(int[] nums, int start, int end, int target){
        if(start >= end){
            return;
        }
        int mid = start + (end - start)/2;
        int pivot = choosePivot(nums[mid], nums[start], nums[end]);
        //int pivot = nums[mid];
        int i = start;
        int j = end;
        while(i <= j){
            while(nums[i] < pivot){
                i++;
            }
            while(nums[j] > pivot){
                j--;
            }
            if(i <= j){
                if(nums[i] != nums[j]){
                    swap(nums, i, j);
                }
                i++;
                j--;
            }
        }
        if(target <= i - 1){
            quicksort(nums, start, i - 1, target);
        }
        else{
            quicksort(nums, i, end, target);
        }
    }
    
    private int choosePivot(int a, int b, int c){
        if(a > b){
            if(c > a){
                return a;
            }
            else if(c > b){
                return c;
            }
            else{
                return b;
            }
        }
        else{
            if(c > b){
                return b;
            }
            else if(c > a){
                return c;
            }
            else{
                return a;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    

    }


  • 0
    L

    it sounds a brilliant idea !


  • 4

    That's called quickselect.


  • 0
    X

    @StefanPochmann wow I didn't know that before, thank you!


  • 0
    F

    The Time complexity of Quick Sort is O(nlogn). But why the implement time is smaller than Quick Select, which is O(n)?


  • 0
    X

    @fei38 For quick sort it's F(n) = n + 2F(n/2) which is nlogn, but for this case it's F(n) = n + F(n/2), we only process the half, so it's not nlogn but approximate O(n)


  • 0
    Y

    @fei38 average O(n), worst O(n^2)


Log in to reply
 

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