高效查找数组中重复元素（线性时间+原地标记法详解）-java教程-PHP中文网

高效查找数组中重复元素（线性时间+原地标记法详解）

本文介绍如何在 o(n) 时间复杂度、仅用返回列表的额外空间前提下，找出 0 到 n−1 范围内整数数组中的所有重复元素，并避免结果中出现重复数值。核心在于利用数组索引与值的映射关系进行原地标记。

本文介绍如何在 o(n) 时间复杂度、仅用返回列表的额外空间前提下，找出 0 到 n−1 范围内整数数组中的所有重复元素，并避免结果中出现重复数值。核心在于利用数组索引与值的映射关系进行原地标记。

在解决“查找数组中重复元素”问题时，许多初学者会本能地选择先排序再遍历比较（如双层循环或相邻扫描），但这种方法存在两个关键缺陷：

时间超标：排序本身为 O(N log N)，不满足题目要求的 O(N)；
结果去重缺失：即使排序后扫描，若仅判断 arr[i] == arr[j]，仍可能将同一重复值多次加入结果（例如 25 出现 3 次，会被添加 2 次甚至更多）。

你提供的代码正是如此：

for(int i=0; i<n i for j="i+1;" if list1.add><p>该逻辑未做“首次发现即记录”的控制，导致 <code>25</code> 在匹配 <code>(i=2, j=13)</code>、<code>(i=2, j=22)</code>、<code>(i=13, j=22)</code> 等多组位置时被重复插入。</p>
<h3>✅ 正确解法：原地哈希标记（O(N) 时间 + O(1) 额外空间）</h3>
<p>题目约束明确指出：“<strong>额外空间仅用于返回列表</strong>”，且数组元素范围为 <code>[0, N−1]</code> —— 这是典型的<strong>原地哈希（in-place hashing）</strong> 适用场景。我们可将数组本身作为哈希表，利用 <code>arr[i] % n</code> 提取原始值，并通过累加 <code>n</code> 的倍数来标记“该值是否已出现过”。</p>
<h4>? 核心思想：</h4>
<ul>
<li>数组中每个合法值 <code>v ∈ [0, N−1]</code> 都能唯一对应一个索引 <code>v</code>；</li>
<li>初始时 <code>arr[v] ，我们约定：若 <code>arr[v] ≥ 2n</code>，则表示值 <code>v</code> 至少出现 2 次；</code>
</li>
<li>遍历原数组，对每个 <code>arr[i]</code>，计算其真实值 <code>val = arr[i] % n</code>，然后执行 <code>arr[val] += n</code>；</li>
<li>第二遍扫描 <code>arr[0..n−1]</code>，若 <code>arr[i] >= 2*n</code>，说明值 <code>i</code> 出现 ≥2 次 → 加入结果。</li>
</ul>
<h4>✅ 完整实现（符合 GFG 要求）：</h4>
<pre class="brush:php;toolbar:false;">import java.util.*;

class Solution {
    public static ArrayList<integer> duplicates(int arr[], int n) {
        ArrayList<integer> result = new ArrayList();
        final int MARK_THRESHOLD = 2 * n; // 标记重复的阈值

        // 第一遍：利用模运算提取原始值，累加 n 实现计数标记
        for (int i = 0; i = MARK_THRESHOLD) {
                result.add(i);
            }
        }

        // 若无重复，返回 [-1]
        if (result.isEmpty()) {
            result.add(-1);
        }

        return result;
    }
}</integer></integer>

⚠️ 注意事项：

不要修改原始值语义：每次访问 arr[i] 前必须用 % n 取模，因为后续元素可能已被标记（如 arr[i] = original + k*n）；
*阈值设为 `2n**：因初始值最大为n−1，一次标记后最大为(n−1)+n = 2n−1，故≥2n` 才能确保至少被标记两次；
无需排序，无需额外哈希结构：完全满足题目对时间（O(N)）和空间（O(1) 辅助空间）的严苛要求；
结果天然有序：因按索引 0→n−1 扫描，result 中元素自动升序排列，符合题目“ascending order”要求。