6.数组中的重复数 | 野渡的博客

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

1、题目描述

https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

2、解题思路

（1）Hash求解（或者排序后求解）

用一个辅助数组进行计数，遍历原数组并记录每个数出现的次数，然后就可以得到重复的数。这种的解法的的时间复杂度为O(n),空间复杂度也为O(n)。实现代码如下：

class Solution {
public:
    // Parameters:
    // numbers: an array of integers
    // length:  the length of array numbers
    // duplication: (Output) the duplicated number in the array number
    // Return value:true if the input is valid, and there are some duplications in the array number; otherwise false
    
    bool duplicate(int numbers[], int length, int* duplication) {
        int *cnt=new int[length]; //辅助数组
        for(int i=0;i<length;i++) cnt[i]=0; //计数都为0
        for(int i=0;i<length;i++)
        {
            if(numbers[i]>=length || numbers[i]<0) return false;
            if(cnt[numbers[i]]>=1) //判断是否重复
            {
                *duplication=numbers[i];
                delete cnt; //记得释放
                return true;
            }
            else cnt[numbers[i]]++;
        }
        delete cnt;//记得释放
        return false;
    }
};

（2）创新解法

依次遍历数组，对于坐标i，取其值m，然后判断numbers[m]是否与m相等，相等则表明对应的位置上已经有该值，返回；否则交换numbers[i]和numbers[m]，将m放到对应的位置，然后继续取numbers[i],直到numbers[i]==i,即当前位置已经被放置。

class Solution
{
public:
    bool duplicate(int numbers[], int length, int *duplication)
    {
        if(numbers==nullptr||length<0) return false;

        for(int i=0;i<length;i++)
        {
            while(i!=numbers[i])
            {
                if (numbers[i] >= length || numbers[i] < 0) return false; //范围出错
                if (numbers[i] == numbers[numbers[i]])  //对应的数已经出现过一次了
                {
                    *duplication = numbers[i]; //找到值
                    return true;
                }
                swap(numbers[i], numbers[numbers[i]]);//一直换，知道换到对应的数为相应的数
            }
        }
        return false;
    }
};

该种解法的时间复杂度为O(n),虽然有两重循环，但是固定位置的数只需要放正确一次即可，无论是while循环还是for循环都来做。空间复杂度为O(1)。

3、类似的题

3.1 长度为n+1的数组放1~n的数，求重复的数（不能修改原数组）。

这个题跟上一个题的数主要区别是不能修改原数组。可以用辅助数组进行求解，还可以用二分法进行求解，如取中间的数m，然后统计1~m的数的个数cnt1，统计m+1~n的数的个数cnt2。如果cnt大于m，则对应的重复的数在1~m这个区间，继续二分，直到最后一个数。

时间复杂度为O(nlogn),空间复杂度为O(1)。

3.2 除了一个数外，所有两个数都出现两次的数组，找出这个数。

用异或可解决问题，时间复杂度为O(n)。

3.3 除了两个数外，所有两个数都出现两次的数组，找出这两个数。

还是用异或进行解决，需要注意的是这里需要求出那两个特殊的数的异或结果，然后找到其为1最低位对应的2的幂值m，遍历数组找到与m相与为1的所有数然后异或即可得结果result1，遍历数组找到与m相与为0的所有数然后异或即可得结果result2。

3.4 除一个数外，其它的所有的数都出现3次，求这个数。

这个题的解法为用一个长度为32的数组，用来统计数组中所有数对应位为1的个数。最后遍历一次处理这个数组即可得到结果。

时间复杂度为O(n),空间复杂度为O(1)。