跳转至

剑指 Offer 03. 数组中重复的数字#

问题描述#

找出数组中重复的数字。


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

示例 1：

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

 

限制：

2 <= n <= 100000

解题思路#

方法一：哈希表标记#

用哈希表标记出现过的数字。

1
2
3
4
5
6
7
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        vis = set()
        for x in nums:
            if x in vis: return x
            vis.add(x)
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> vis;
        for (auto x : nums) {
            if (vis.find(x) != vis.end()) return x;
            vis.emplace(x);
        }
        return -1;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)

方法二：数组标记#

因为数字的范围已经给定了，所以可以直接使用数组来标记出现过的数字。

1
2
3
4
5
6
7
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        vis = [False] * len(nums)
        for x in nums:
            if vis[x]: return x
            vis[x] = True
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<bool> vis(nums.size());
        for (auto x : nums) {
            if (vis[x]) return x;
            vis[x] = true;
        }
        return -1;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)

方法三：用正负号来标记数字#

对于每个数字，我们将这个数字作为下标索引位置上的数字变为相反数，这样下次这个数字出现时，我们就可以根据该位置上数字的符号来判断了。

因为数字 \(0\) 的存在，导致正负号失去作用，所以首先对原数组中的每个数都增加 \(1\)，遍历时再减去 \(1\) 即可。

1
2
3
4
5
6
7
8
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        nums[:] = [x + 1 for x in nums]
        for x in nums:
            x = abs(x)
            if nums[x - 1] < 0: return x - 1
            nums[x - 1] = -nums[x - 1]
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (auto &x : nums) ++x;
        for (auto x : nums) {
            x = abs(x);
            if (nums[x - 1] < 0) return x - 1;
            nums[x - 1] = -nums[x - 1];
        }
        return -1;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(1)\)

方法四：索引标记#

类似方法三，只不过我们是将数字交换回它所在的索引，使得 \(\texttt{nums}[i]=i\)，如果下次遇到 \(\texttt{nums}[i]!=i\) 但是 \(\texttt{nums}[\texttt{nums}[i]]=\texttt{nums}[i]\)，就说明 \(\texttt{nums}[i]\) 重复了。

1
2
3
4
5
6
7
8
9
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i, _ in enumerate(nums):
            while i != nums[i]:
                if nums[nums[i]] == nums[i]: return nums[i]
                tmp = nums[nums[i]]
                nums[nums[i]] = nums[i]
                nums[i] = tmp
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size(), tmp;

        for (int i = 0; i < n; ++i) {
            while (i != nums[i]) {
                if (nums[nums[i]] == nums[i]) return nums[i];
                tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }
        return -1;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(1)\)

返回顶部

在手机上阅读