《leetCode》：Find the Duplicate Number

题目: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(n2).
• There is only one duplicate number in the array, but it could be repeated more than once.

思路

• 思路一：可以用排序来做，但是限制了不允许打乱数组，

  借助额外的空间 来完成也不行，因为题目也限制了

• 思路二：用暴力搜索也不行，限制了时间复杂度小于O(n*n)
• 思路三：来源于：https://leetcode.com/discuss/89038/o-32-n-solution-using-bit-manipulation-in-10-lines

We can count the sum of each 32 bits separately

for the given array (stored in “b” variable) and for the array [1, 2, 3, …, n] (stored in “a” variable).

If “b” is greater than “a”, it means that duplicated number has 1 at the current bit position

(otherwise, “b” couldn’t be greater than “a”). This way we retrieve the answer bit by bit:

实现代码如下：

int findDuplicate(int* nums, int numsSize) {
    if(nums==NULL||numsSize<){
        return -;
    } 
    int res=;
    for(int i=;i<;i++){
        int bit=<<i;
        int a=;
        int b=;
        for(int j=;j<numsSize;j++){
            if(j&bit){
                a++;
            }
            if(nums[j]&bit){
                b++;
            }
        }
        if(b>a){
            res+=bit;
        }
    }
    return res; 
    }
           

小结

由于题目有很多的限制，因此，题目无形之中就变的难的多了，在讨论组看到的方法确实很经典也。