AC Clean QuickSelect Java solution avg. O(n) time


  • 91

    https://en.wikipedia.org/wiki/Quickselect

    public class Solution {
      
      public int findKthLargest(int[] a, int k) {
        int n = a.length;
        int p = quickSelect(a, 0, n - 1, n - k + 1);
        return a[p];
      }
      
      // return the index of the kth smallest number
      int quickSelect(int[] a, int lo, int hi, int k) {
        // use quick sort's idea
        // put nums that are <= pivot to the left
        // put nums that are  > pivot to the right
        int i = lo, j = hi, pivot = a[hi];
        while (i < j) {
          if (a[i++] > pivot) swap(a, --i, --j);
        }
        swap(a, i, hi);
        
        // count the nums that are <= pivot from lo
        int m = i - lo + 1;
        
        // pivot is the one!
        if (m == k)     return i;
        // pivot is too big, so it must be on the left
        else if (m > k) return quickSelect(a, lo, i - 1, k);
        // pivot is too small, so it must be on the right
        else            return quickSelect(a, i + 1, hi, k - m);
      }
      
      void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
      }
    
    }

  • 0
    F

    one question.
    while (i < j) {
    if (a[i++] > pivot) swap(a, --i, --j);
    }.

    why --i,--j, I think should simple swap(i,j)


  • 11

    Hi FanFeng, in quick sort, I pick a[hi] as the pivot, and set i = lo, j = hi, our mission is to put all the numbers that are greater than the pivot to the right, and all the numbers that are less than or equal to the pivot to the left, so let's take a look at this example:

    lo ----- hi

    5 2 1 4 3

    i ------- j

    3 is the pivot, since 5 (a[i++]) > pivot, let's put 5 to the right, to do that, we swap 4 and 5, so it becomes to:

    4 2 1 5 3

    i ----- j

    now since 4 is larger than pivot, we swap 4 and 1, we get:

    1 2 4 5 3

    i --- j

    as you can see, --i makes sure we can still check a[i] after the swap, and --j makes sure we won't overwrite the ones that are already done. Hope that makes sense to you.


  • 0
    F

    i see your point. great idea. thx


  • 1
    Z

    do you consider duplicated value?
    like {1,2,3,3,4,5}, the 4th largest should be 2 not 3.


  • 3
    M

    I guess what you mean is the 4th largest number should be 4.
    But this question has one requirement.

    Note that it is the kth largest element in the sorted order, not the kth distinct element.

  • 0
    W

    I want to upvote your comment.


  • 0

    4th largest means count from largest to smallest......it is 3


  • 1

    OMG so stunning. Hands Upppp and vote!


  • 0

    is there something with that sentence?
    if (m == k) return i;
    i think it should be
    return a[i];


  • 0
    H
    // put nums that are <= pivot to the left
    // put nums that are  > pivot to the right
    int i = lo, j = hi, pivot = a[hi];
    while (i < j) {
      if (a[i++] > pivot) swap(a, --i, --j);
    }
    swap(a, i, hi);
    

    Can someone please point out why it's putting nums that are <= pivot to the left?


  • 1
    B

    @happyLucia
    I think it's because int p = quickSelect(a, 0, n - 1, n - k + 1); has converted the problem into find (n-k+1)th smallest.


  • 0
    H

    @Badger96 Thanks for your reply. I didn't make my question clear. Actually I meant to ask:
    it seems it's swapping a[i] with a[j]. while a[i] is > pivot for sure, it didn't check if a[j] < pivot or not.
    Did I miss anything here? How do you think?


  • 0
    I

    if (m == k) return i;

    what's the reason you return i here? I tried returning a[i] but it gives me wrong answer. I thought i is supposed to be an index?


  • 0
    Z

    why is k-n+1 in the beginning?


  • 0
    R

    @zfrancica Since the quickSelect method is to find the kth smallet number, and we need to find the kth element, so we need convertsion here.


  • 3
    L

    why always use ++ and -- in this way? really unreadable....


  • 8

    Here's an iterative version of same idea. Note that we only shrink the range between l and r but never change k. Thanks for sharing!

        public int findKthLargest(int[] A, int k) {
            k = A.length - k; // convert to index of k largest
            int l = 0, r = A.length - 1;
            while (l <= r) {
                int i = l; // partition [l,r] by A[l]: [l,i]<A[l], [i+1,j)>=A[l]
                for (int j = l + 1; j <= r; j++)
                    if (A[j] < A[l]) swap(A, j, ++i);
                swap(A, l, i);
    
                if (k < i) r = i - 1;
                else if (k > i) l = i + 1;
                else return A[i];
            }
            return -1; // k is invalid
        }
    

  • 0
    Q

    @jeantimex why is j-- ?why not --j?--j make the greater 3 number on the 3 left such as 4 2 1 5 3


  • 0
    G

    Hi Guys,

    Actually, there is no need to calculate the count and do "k-m"

    Here is the simplified logic, just keep track of the pivot index after each partition. The count would be p + 1,
    and for all the subproblems can use "k" instead of "k- m";

            int p =  part(nums, nums[pivotIndex], s, e);
            int count = p + 1;
            if (count == k) {
                return nums[p];
            } else if (count > k) {
                return findKthLargest(nums, s, p - 1, k);
            } else {
                return findKthLargest(nums, p + 1, e, k);
            }
    

Log in to reply
 

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