287 Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

• Note:
  • You must not modify the array (assume the array is read only).
  • You must use only constant, $$O(1)$$ extra space.
  • Your runtime complexity should be less than $$O(n^2)$$.
  • There is only one duplicate number in the array, but it could be repeated more than once.

Solution

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size()-1;
        if ( n <= 0 ) return 0;
        int l = 1, r = n;
        int mid = 0, lt = 0, gt = 0;
        while ( l <= r-1 ) {
            mid = 0; lt = 0; gt = 0;
            for ( int i = 0; i <= n; i++ ) {
                if ( (l+r)%2 == 0 ) {
                    if ( nums[i] == (l+r)/2 ) mid += 1;
                    if ( mid == 2 ) return (l+r)/2;
                }
                if ( nums[i] >= l and nums[i] <= (l+r-1)/2 ) lt += 1;
                if ( nums[i] <= r and nums[i] >= (l+r+2)/2 ) gt += 1;
            }
            if ( lt > gt ) r = (l+r-1)/2;
            if ( lt < gt ) l = (l+r+2)/2;
        }
        return r;
    }
};

Notes
抽屉原理！
For the first scan, there are $$(n+1)$$ numbers lying in the inclusive interval $$[1, n]$$.

• If $$(1+n)$$ is odd, the larger half have at least $$\frac{n}{2} + 1$$ numbers. (The new interval is either $$[1, \frac{n}{2}]$$ or $$[\frac{2+n}{2}, n]$$, interval length is $$\frac{n}{2}$$.)
• If $$(1+n)$$ is even, one has to take special care of the "middle number". The larger have at least $$\frac{n+1}{2}$$ numbers. (The new interval is either $$[1, \frac{n-1}{2}]$$ or $$[\frac{n+3}{2}, n]$$, interval length is $$\frac{n-1}{2}$$.)

Note in the new situations, the following relation still holds: In the "larger half" interval $$[l, r]$$, there are always at least $$(r-l+2)$$ numbers. Thus there must be a duplicate number lying in that interval.