【leetcode】8. 数组-数组中重复的数字

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

题目

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

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
 
限制：
2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

本题解法很多。注意两点：

  1. 查找：想到随机查找（数组下标、关联容器key）
  2. 所有数字都在 0～n-1 的范围内：可以利用数据下标
  3. 找出数组中任意一个重复的数字

解法一

分析

可以再遍历数组的同时对每一个元素做一个标记，这个标记是可以在O(1)时间复杂度获取的，继续遍历数组，并判断元素标记，如果已经存在，则直接返回，否则改变标志。具体流程如下：

  1. 创建一个map<int, bool> ret
  2. 遍历数组nums,如果ret[nums[i]] 不存在，则ret[nums[i]] = true；如果ret[nums[i]] = true，则返回nums[i]

tips：步骤1种使用map并不是最优的,也可以使用set。在数组元素重复的比较少的时候可以使用vector。

时间复杂度：O(N)
空间复杂度：O(N)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        map<int, bool> ret;// 使用map
        for (int i = 0; i < nums.size(); i++) {
            if (ret.count(nums[i]) == 0) {
                ret[nums[i]] = true;
            } else {
                return nums[i];
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<bool> ret(nums.size(), false);// 使用vector
        for (int i = 0; i < nums.size(); i++) {
            if (ret[nums[i]] == false) {
                ret[nums[i]] = true;
            } else {
                return nums[i];
            }
        }
        return  -1;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        set<int> ret;// 使用set
        for (int i = 0; i < nums.size(); i++) {
            if (!ret.insert(nums[i]).second) {
                return nums[i];
            }
        }
        return -1;
    }
};

解法二

分析

本题并没限制不能改变原有数组nums，同时强调，所有数字都在 0～n-1 的范围内。因此，可以将元素nums[i]移动到nums[nums[i]]：

  1. 当nums[i] == i,说明i位置上的元素已经是i了，不做任何处理，继续遍历
  2. 当nums[i] == nums[nums[i]]，说明nums[i]位置的元素已经是nums[i],说明重复了，返回nums[i]即可
  3. 当上述两个条件都不满足的时候，交换一下

时间复杂度：O(N)
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == i ) {
               continue;
            } else if (nums[i] == nums[nums[i]]) {
                return nums[nums[i]];
            } else {
                int tmp = nums[i];
                nums[i] = nums[nums[i]];
                nums[tmp] = tmp;
            }
        }
        return -1;

    }
};