Binary Search Answer, O(N * constant)


  • 0
    F

    The idea is to search for the answer, and check whether the given answer is at Kth maximum position.

    Given the range of all possible value, we can narrow down the range of final results by using binary search. For example, the range of all possible value is 0 .. 100,

    1. we first try whether mid-value (e.g. 50) is the Kth maximum position.
    2. To verify, we scan the array and count how many elements are greater than or equal to 50.
    3. if the count > K, then the real answer should be greater than mid-value (e.g. 50), we search answer in 51 ... 100; otherwise, the real answer should be less than mid-value, we search answer in 0..50

    Every time, It takes O(N) to verify the position of the current result.
    It will take O(log C) times to do the verification, where C is the range of the possible value, which we can treat it as O(1)

    # @param {Integer[]} nums
    # @param {Integer} k
    # @return {Integer}
    def find_kth_largest(nums, k)
        min, max = nums[0], nums[0]
        nums.each {|x| 
            min = [min, x].min
            max = [max, x].max
        }
        while min <= max 
            mid = (min + max) / 2
            count = 0;
            nums.each{|x| count += 1 if x >= mid}
            if count >= k
                min = mid + 1
            else
                max = mid - 1
            end
        end
        return max
    end

  • 0

    A rather "bold" move to treat the range as O(1). But whatever, I like the idea, and I like Ruby :-) Here's a shorter version, though:

    def find_kth_largest(nums, k)
        min, max = nums.minmax
        while min <= max 
            mid = (min + max) / 2
            if nums.count{|x| x >= mid} >= k
                min = mid + 1
            else
                max = mid - 1
            end
        end
        max
    end
    

  • 0
    F

    wow! Thanks Stefan, your code is really elegant!!


  • 0

    Ruby is such a treasure trove, you just need to use it all :-). I just came across each_cons while solving another problem. Mind-blowing. I'm a Ruby beginner and I'm already loving it.


  • 0

    "you just need to use it all", lol. What a newb I was :-). I just did this again, now in one line by using bsearch.


Log in to reply
 

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