"O(n)" one-liner Ruby


  • 0

    Actually it's O(wm) where w is the word size, 32 (bits). Like radix sort, for example.

    I do a binary search in the unsigned 32-bit int range, looking for the smallest number that covers the kth place from the end. Which is the smallest number with fewer than k numbers in nums larger than it.

    def find_kth_largest(nums, k)
      (-2**31...2**31).bsearch { |i| nums.count { |x| x > i } < k }
    end
    

    An optimization:

    Instead of the full possible range, I only search the actual range found in nums. Finding that range costs extra time, but it more than makes up for it by reducing the number of bsearch rounds. I tested each three times and this version was consistently significantly faster. Best for each was 100 ms and 132 ms, respectively.

    def find_kth_largest(nums, k)
      (nums.min..nums.max).bsearch { |i| nums.count { |x| x > i } < k }
    end

Log in to reply
 

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