本文共 2128 字，大约阅读时间需要 7 分钟。

03.数组中的重复数字

一、题目：

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：

[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3

限制：

2 <= n <= 100000

来源：力扣（LeetCode）

二、思路和代码：

方法一：暴力超市

双重循环，从头到尾，依次比较这个数字和它的后面数字比较。时间复杂度O（n²）。超出时间限制，就很不聪明的亚子。 代码如下：

class Solution {public:    int findRepeatNumber(vector
   
    & nums) {        for(int i=0;i
   

方法二：排序+遍历：

使用sort()排好序的数组一定是按照非递减的顺序依次排列的，当某个数和他的下一位一样的时候就出现了重复，nice!

class Solution {public:    int findRepeatNumber(vector
   
    & nums) {        sort(nums.begin(),nums.end());        int i=1;        for(;i
   

方法三：哈希表

使用哈希表，将每个数字存入哈希表，如果哈希表中的值为2了，说明之前已经存过一次了，就重复了，返回该值即可。 PS：改进：如果题目是统计所有重复值，也可以使用哈希表，将表中值大于1的输出。

class Solution {public:    int findRepeatNumber(vector
   
    & nums) {        unordered_map
    
     map;        for(auto & num:nums){            map[num]++;            if(map[num]>1)return num;        }        return 0;    }};
    
   

你以为这就结束了？仔细看题，还有一个巧妙的条件没有用：数值都位于0-n-1之间！也就是说，如果没有重复值的话，数组中的值就是0-n-1；似乎可以拿来搞事情，划掉，搞代码。没错！

方法四：原地置换

有了上面的分析以后，继续。 1、i从0-n-1xunhuan 2、如果第i个对应的数字刚好就是i,也就是nums[i]==i,那没事了，下一个； 3、如果如果第i个对应的数字不是i,也就是nums[i]！=i，那么就将nums[nums[i]]和nums[i]比较，如果一样就说明有重复，且数字就是nums[i]，因为它在num[i]和i都出现了;如果不一样就将nums[i]和nums[nums[i]]交换，把nums[nums[i]]放在其该在的位置(其实这也可以是看做在排序)，再次从第二步开始判断。

以题目中的[2, 3, 1, 0, 2, 5, 3]举个例子，多带入代码循环几次就懂了。

[2, 3, 1, 0, 2, 5, 3]//原来的样子 [1, 3, 2, 0, 2, 5, 3]//nums[0]!=0,比较nums[nums[0]]和nums[0]，nums[2]=1,nums[0]=2;不相等，交换，结果就是前面的数组； [3, 1, 2, 0, 2, 5, 3]//nums[0]!=0,比较nums[nums[0]]和nums[0]，nums[3]=0,nums[0]=3;不相等，交换，结果就是前面的数组； [0, 1, 2, 3, 2, 5, 3]//nums[0]等于0,下一个；nums[1]等于1,下一个；… ，一直到i==3,i和num[i]都相等，比较下一个，在此过程中数组的样子不变 [0, 1, 2, 3, 2, 5, 3]//nums[4]!=4,比较nums[nums[4]]和nums[4]，nums[2]=2,nums[2]=2;相等，找到了重复数字num[i]。 代码如下：

class Solution {public:    int findRepeatNumber(vector
   
    & nums) {        int i=0;        while(i
   

还有什么问题吗？

比较：

方法一：暴力搜索不需要开辟新空间，定义两个变量即可，但是耗时耗力，复杂度O（n²），很不好； 方法二：排序后时间复杂度O（nlogn）,主要是排序函数所花费的时间，然后遍历一次数组即可，比1快很多； 方法三：哈希表需要定义一个map，然后遍历一次数组即可，时间复杂度为O(n)，但是实际上从提交结果来看占用时间、空间比2要多一些； 方法四：原地置换需要遍历一次数组即可，时间复杂度o(n),定义一个用来循环的下标i就行了，也不需要别的额外的空间了，结果上来看是最优的。

怕什么真理无穷，进一寸有进一寸的欢喜。

如有不足，欢迎指正！

转载地址：http://uiexi.baihongyu.com/