442. 数组中重复的数据

1. 题目简介

难度：中等，原题链接：442. 数组中重复的数据。

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

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

2. 问题分析

可以借用原数组记录每个数字出现了几次：数字 t 对应下标 t - 1，每遇到一次 t，就给 nums[t - 1] 加上 n。这是 448. 找到所有数组中消失的数字中原地标记方法的延伸。

修改数组之后，扫描到的值可能已经被加过若干次 n。但加上 n 的整数倍不会改变取模结果，因此 (nums[i] - 1) % n 仍然是原始数字对应的下标。这里先减 1，是为了把值域 [1, n] 映射到下标范围 [0, n - 1]。

原始元素在 [1, n] 内，所以计数完成后：

• 数字 t 出现一次，对应位置的值在 [n + 1, 2n] 内。
• 数字 t 出现两次，对应位置的值在 [2n + 1, 3n] 内。

题目保证每个数字最多出现两次，因此检查 nums[i] > 2 * n，就能找出重复数字 i + 1。代码中的 nums[i] - 2 * n > 0 表达的是同一个条件。

3. 代码实现

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 1. 数字 t 对应的数组下标为 t - 1
            // 2. 当前元素可能已经被变换过，所以需要取模
            int target = (nums[i] - 1) % n;
            nums[target] += n;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] - 2 * n > 0) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

4. 复杂度分析

• 时间复杂度：O(n)，两次扫描分别累计次数和收集答案。
• 额外空间复杂度：O(1)，不计返回结果所占的空间；出现次数保存在原数组中。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明