力扣×剑O 03. 数组中重复的数字

发表于 更新于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

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

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

限制：
2 <= n <= 100000

由于题目中提到了“长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内”，很自然的，第一种思路是新建一个新的等容量的vector容器ind，其中每个元素都默认初始化为0，代表每个元素出现了0次。之后对原vector容器遍历，每次将ind[nums[i]]加一，代表该元素出现了一次。如果加一之后发现该元素值>1，说明这个元素出现了两次，此时直接返回元素i。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<int> ind(nums.size());  //其实第二个vector充当了哈希表的角色
        //但是由于没有真正计算hash，效率会更更高
        for(auto &i: nums){
            ++ind[i];
            if(ind[i]>1)
                return i;
        }
        return -1;    
    }
};
上面是我的代码结果，下面是别人的hash方法代码结果

看了评论才知道，这道题并没有这么简单，实际上还会考察时间、空间权衡的因素，也就是说，这道题需要分情况讨论

上面的代码属于时间优先，代码运行两次，运行时间分别是99%和100%。从时间的角度来说，这种方法已经足够了；
空间优先的情况下，需要原地对原数组进行排序，我采用了选择排序。

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        if(nums.size()==2)
            return nums[0];
		for (auto i = nums.begin()+1; i != nums.end(); i++)//未排序的数字从第二个开始
		{
			int key = *i;  //插入的值
			auto move = i;    //用于移动的指针
			while(move>nums.begin() && *(move-1)>key){  //只要前面还有更大的数,而且没有到头
                 *(move)=*(move-1);
                move--;
            }
             //下面的这两行用于解题，不属于插入排序：
             //如果插入前前面有同样大的数（while循环跳过了所有比key大的数）
             //说明有重复，直接返回
            if( move!=nums.begin()  &&*(move-1)==key)  
                return key;
            *(move)=key;
		}
        return -1;
    }
};

20201114151949.png

运行两次（下两行）的实际效果与sort排序（第一行）的对比

书上（《剑指Offer：名企面试官精讲典型编程题（第2版）》39页）还有下面这种思路不错的方法：

现在让我们重排这个数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i 的数字时，首先比较这个数字（用 m 表示 ）是不是等于i。如果是 ，则接着扫描下一个数字；如果不是，则再拿它和第 m 个数字进行比较 。如果它和第 m 个数字相等，就找到了一个重复 的数字（该数字在下
标为i和m的位置都出现了）；如果它和第 m 个数字不相等，就把第i个数字和第m个数字交换， 把m放到属于它的位置。接 下来再重复这个比较、交换的过程，直到我们发现一个重复的数字 。

以数组 {2, 3, l , 0, 2, 5, 3} 为例来分析找到重复数字的步骤。 数组的第 0个数字（从 0 开始计数，和数组的下标保持一 致）是 2, 与它 的下标不相 等，于是把它和下标为 2 的数字 1 交换 。交换之后的数组是 { I, 3, 2, 0, 2, 5, 3} 。此时第 0 个数 字是 I , 仍然与它 的下标不相等 ， 继续把它和下标为 1 的数字3 交 换，得到数 组 {3, I, 2, 0, 2, 5, 3} 。 接下来继续交换第 0 个数 字 3 和 第 3个数字 0, 得到数组 {O, I, 2, 3, 2, 5, 3} 。 此时第 0 个数字 的数值为 O, 接着扫描下一个数字。在接下来的几个数字 中，下标为 1 、 2 、 3 的 3 个数字分
别为 l 、 2 、 3, 它们的下标和数值都分别相等，因此不需要执行任何操作 。接下来扫描到下标为 4 的数字2 。 由千它的数值与它的下标不相等 ， 再比较它和下标为 2 的数字 。注 意到此时数组中下标为 2 的数字也是 2, 也就是数字 2 在下标为 2 和 下标为 4 的两个位置都出现了，因此找到 一个 重复的数字。

总体思路：就是利用了原数组作为哈希表，将各个数字归位、放回对应的nums[i]，在这个过程中如果某次归位前遇到了nums[i]=i，说明已经有重复的数字i了，则立即返回。
具体解法：遍历下标0到n-1，每个下标都检查归位，具体归位过程分为三种情况：

  • 情况一：已经i=nums[i]，此时直接跳过即可
  • 若i和nums[i]不相等，i的位置存放了数字j(即j=nums[i])。又像上面分为两种情况：
    • 情况二：如果j=nums[j]，即((nums[nums[i]])=nums[j])，那么说明有重复，直接返回j
    • 情况三：如果j和nums[j]不相等，nums[j]的位置存放了数字k(即k=nums[j])。那么可以直接将j和k两个数置换一下，将j放回他的位置nums[j]，k放到num[i]。
      需要注意的是，只有j(nums[i])和k(nums[j])才是nums中存储的元素，i只是一个下标用于遍历（j既充当下标又是数组中元素）。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0;i< nums.size();i++){
            if (i==nums[i])continue;  //情况一
            int j = nums[i], k= nums[j];
            if (k== j) return j;  //情况二
            nums[i] = nums[j];   //情况三
            nums[j]= j;
        }
        return -1;
    }
};

实际运行效果

实际运行效果

BTW:关于空间复杂度，看力扣提交记录里面的内存消耗应该是不准的，把空间消耗战胜100%用户的代码直接复制过来，运行结果只有45%-50%。