Luobuyu's Blog

0%

442. 数组中重复的数据

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 670 阅读时长 ≈ 1 分钟
考虑交换，不能考虑环了。

442.数组中重复的数据

题目描述：

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

数据范围：

$1\le n \le 10^5$

题解：

考虑把每个数放到原来的位置，这样剩下的 $nums[i] \neq i - 1$ 的元素就是重复元素了。

如何放？

可以考虑 $nums[i]$ 和 $nums[nums[i] - 1]$ ，如果不相同就交换。

不能直接 while(i != nums[i - 1])，这样的话很可能会死循环。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    vector<int> findDuplicates(vector<int> &nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            while (nums[i] != nums[nums[i] - 1])
            {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i)
        {
            if (nums[i] - 1 != i)
            {
                ans.emplace_back(nums[i]);
            }
        }
        return ans;
    }
};