Java O(1)space using Binary-Search


  • 53
    6
    public int findDuplicate(int[] nums) {
    	int low = 1, high = nums.length - 1;
        while (low <= high) {
            int mid = (int) (low + (high - low) * 0.5);
            int cnt = 0;
            for (int a : nums) {
                if (a <= mid) ++cnt;
            }
            if (cnt <= mid) low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }

  • 2
    Q

    good method, the wise use of number density and binary search, so smart!

    For "int mid = (int) (low + (high - low) * 0.5);", you would better to use int instead of double, which can be much faster.


  • 0
    6

    thiank your remind.


  • 0
    B
    This post is deleted!

  • 0
    W

    This does not fly since you assume that the count of elements on one side of mid will be enough to tell you where the repeated element is. This is not always the case. Consider:

    0 1 2 2 2 5 6 7 8 9 10. mid is 5 and the count on either side is unchanged by the repeated element. You still need to inspect both segments.


  • 0
    W

    I think he used binary-search method, but the complexity is O(n) rather than O(logn). However, it is still a pretty good algorithm which I can not work out by myself. :-(


  • 3
    F

    I think it's O(nlogn)


  • 0
    L

    Input is from 1 to n, 0 is not valid input.


  • -1
    W

    Regardless. Binary search in this way will not work since counting member on either side of the mid-point is not sufficient to determine where the repeat number is. Modified example
    1 2 2 2 5 6 7 8 9 10 11
    2 is repeated 2 more times. midpoint is 6. count is 5 on both sides of the midpoint. count cannot differentiate where the repeat number is.


  • 2
    W

    This does not fly since you assume that the count of elements on one side of mid will be enough to tell you where the repeated element is. This is not always the case. Consider:
    1 2 2 2 5 6 7 8 9 10 11. mid is 6 and the count on either side is unchanged by the repeated element. You still need to inspect both segments.


  • 0
    G

    In your case, max num is 11, so you at least have 12 elements, according to the question description "n + 1 integers where each integer is between 1 and n (inclusive)".


  • 0
    W

    Thanks @GodHelpMe. It makes sense now.


  • 0
    L

    As @GodHelpMe noted this is still invalid input, not long enough. If you add another 2 it works as intended.


  • 0
    C

    How could this meet the speed requirement? The worst case running time for this algorithm is O(n2). Worst case is that the dup number happens to be the median, which happens to reside in the middle of the array. Each round takes O(n), n/2 rounds are needed to locate the dup number therefore running time O(n2).

    e.g. 1 2 3 4 5 5 6 7 8 9


  • 0
    B

    Your case is nlogn


  • 0
    H

    why low starts from 1?


  • 0
    R

    Not sure if you are asking for an explanation of this solution or if you could not come up with the solution.

    The complexity is O(logn) for the while loop times O(n) for the inner for loop => O(nlogn). In order to achieve better than O(n^2) we need to divide and conquer to get a log factor complexity. we know that the lowest num is 1 and the highest is n - 1 so we choose the middle and then count the numbers in the array that are less than or equal to it. That way we can tell if the duplicate is closer to left (count > middle) or to high i.e. which side of mid it lies on and thereby we can halve the problem set each iteration.


  • 2
    E

    @han38 the 'low' here means the smallest num that can possibly exist in the nums[], since according to "n + 1 integers where each integer is between 1 and n (inclusive)" , so all the numbers are in [1, n] ([1, nums.length-1])


  • -1
    I
    This post is deleted!

  • 0
    S
    This post is deleted!

Log in to reply
 

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