O(N) with Quick Select


  • 0
    I

    This is a classic quick select problem.

    Note:

    There is a notable improvements to randomised inputs. I forgot to shuffle the nums in my first attempt, ending up 2000+ms. Then I added the shuffle method, getting 98ms.

    A little wrap-up for myself:

    1. In this case, without shuffling, it's O(N) average, but O(N^2) in worst case. With shuffling, it guarantees O(N) in worst case.
    2. Always remember to shuffle when using the 'quick' family algorithms
      def find_kth_largest(nums, k)
        shuffle!(nums)
    
        k -= 1
        # kth largest is the (length-1-k)th smallest
        k = nums.count - 1 - k
    
        lo, hi = 0, nums.count-1
    
        loop do
          break if lo >= hi
          j = partition(nums, lo, hi)
    
          if j == k
            return nums[k]
          elsif j < k
            lo = j + 1
          else
            hi = j - 1
          end
        end
    
        nums[k]
      end
    
      def shuffle!(nums)
        (1..nums.count-1).each do |i|
          j = rand(i+1)
          swap(nums, i, j)
        end
      end
    
      def partition(array, lo, hi)
        v = lo
        i, j = lo, hi+1
    
        loop do
          loop do
            i += 1
            break if i == hi or array[i] >= array[v]
          end
    
          loop do
            j -= 1
            break if j == lo or array[j] <= array[v]
          end
    
          break if i >= j
          swap(array, i, j)
        end
    
        swap(array, j, v)
        return j
      end
    
      def swap(array, i, j)
        t = array[i]; array[i] = array[j]; array[j] = t
      end
    
    

Log in to reply
 

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