2ms Java Sol that beats 95.6% using Quick Select with stupid pivot selection


  • 0

    picking the pivot in the most simple idiot way ever using (left + right) / 2. Anything that would involve Math.random would be more expensive since Math.random are expensive, a better option is to use ThreadLocalRandom because this generate random
    in the running thread (not shared) only and doesn't concern itself with other threads

    // a direct implementation of the algorithm found here
    // https://en.wikipedia.org/wiki/Quickselect#Algorithm
    public int findKthLargest(int[] nums, int k) {
            int nthElementIndex = nums.length - k;
            return select(nums, 0, nums.length - 1, nthElementIndex);
        }
        
        public int select(int[] nums, int left, int right, int nth) {
            if(left == right)
                return nums[left];
            int pivotIndex = (left + right) / 2;
            pivotIndex = partition(nums, left, right, pivotIndex);
            if(pivotIndex == nth)
                return nums[pivotIndex];
            else if(pivotIndex > nth)
                return select(nums, left, pivotIndex - 1, nth);
            else
                return select(nums, pivotIndex + 1, right, nth);
        }
        
        int partition(int[] nums, int left, int right, int pivotIndex) {
            int pivotVal = nums[pivotIndex];
            int ptr = left;
            swap(nums, pivotIndex, right);
            while(ptr < right) {
                if(nums[ptr] < pivotVal) {
                    swap(nums, left, ptr);
                    left++;
                }
                ptr++;
            }
            swap(nums, left, right);
            return left;
        }
        
        void swap(int[] a, int i, int j) {
            int tmp = a[i];
    		a[i] = a[j];
    		a[j] = tmp;
        }
    

  • 0
    M

    This code may work well for some test cases. However it works very bad when it meet some inputs which have lots of same element. For example, the input is [1, 2, 2, 2, 2, 2, ..., 2, 2, 2, 2, 2] which length is 10000 and the k = 9999. In this case, you may receive StackOverflowError Exception when you run this code. The reason is that though you get a approximately well pivotIndex = (left + right) / 2, you would always get a bad pivotIndex after you excute partition function in this case.


  • 0

    @MarvinCao Your are right that this way of picking the random is not a practical, that's true hence the "stupid" in the title :)

    However I gotta mention that the specific test case you are talking about where we have an array of 10000 and we want the 9999, picking this pivot is actually fast and the best in this case, everytime we do (left + right) / 2 and then decide whether we go right or left, we're throwing exactly half the array. So we're gonna get the 9999 largest element in exactly Log10000 base 2, in 14 steps only you will get the solution.

    Again I want to stress on this should be production code, it's definitely bad way to pick the pivot, I just wanted to analyze the specific test you're talking about.

    Also on the same topic, using Math.Random in Java in this algorithm is bad, Math.Random is usually slow.


Log in to reply
 

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