Java实现数组中首个重复元素查找（O(n)时间复杂度）

嘿，这个问题我之前刷算法题的时候也碰到过！你现在写的O(n²)解法应该是嵌套循环逐个比对吧？确实，要降到O(n)的话，核心就是用哈希表来帮我们快速记录和查询元素的出现情况，不用再反复遍历数组啦。

核心思路 #

我们需要在单次遍历数组的过程中，记录每个元素第一次出现的索引。当遇到重复元素时，要比较它的重复位置（当前索引）和已经找到的候选元素的重复位置，保留重复位置更早的那个元素。如果遍历完都没找到重复元素，直接返回-1就行。

Java代码实现（通用版） #

这个版本用HashMap存储元素和它第一次出现的索引，不管数组元素的范围是什么都能用：

import java.util.HashMap;

public class FirstDuplicateFinder {
    public static int findFirstDuplicateWithEarlierIndex(int[] arr) {
        // 存储元素 -> 第一次出现的索引
        HashMap<Integer, Integer> firstOccurrenceMap = new HashMap<>();
        int result = -1;
        // 记录当前找到的重复元素的最早重复位置，初始设为数组长度（比所有索引都大）
        int earliestDuplicatePos = arr.length;

        for (int i = 0; i < arr.length; i++) {
            int currentNum = arr[i];
            if (firstOccurrenceMap.containsKey(currentNum)) {
                // 这个元素之前出现过，拿它第一次出现的索引
                int firstPos = firstOccurrenceMap.get(currentNum);
                // 当前索引i就是它重复的位置，和已记录的最早重复位置比
                if (i < earliestDuplicatePos) {
                    earliestDuplicatePos = i;
                    result = currentNum;
                }
            } else {
                // 第一次遇到这个元素，把它的索引存起来
                firstOccurrenceMap.put(currentNum, i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // 测试你的例子
        int[] testArr1 = {1,4,3,5,3,2,1};
        System.out.println(findFirstDuplicateWithEarlierIndex(testArr1)); // 输出3

        // 测试无重复的情况
        int[] testArr2 = {2,5,7,9,11};
        System.out.println(findFirstDuplicateWithEarlierIndex(testArr2)); // 输出-1
    }
}

代码关键点解释 #

1. 时间复杂度：哈希表的containsKey和put操作平均都是O(1)，所以整个遍历下来是O(n)的时间复杂度。
2. 重复元素的判断逻辑：比如你的例子里，1第一次出现在索引0，重复在6；3第一次出现在2，重复在4。因为4比6小，所以3的重复位置更早，最终返回3。
3. 无重复场景处理：如果数组里没有重复元素，整个遍历过程中不会触发containsKey为true的分支，result会保持初始的-1，直接返回即可。

空间优化版（元素范围有限时） #

如果你的数组元素都是1到数组长度之间的正整数，可以用数组本身来标记元素是否出现过，这样能把空间复杂度降到O(1)（不需要额外的哈希表）：

public class OptimizedFirstDuplicateFinder {
    public static int findFirstDuplicateOptimized(int[] arr) {
        int result = -1;
        int earliestDuplicatePos = arr.length;

        for (int i = 0; i < arr.length; i++) {
            int currentNum = Math.abs(arr[i]);
            // 用元素值对应的索引位置标记是否出现过（负数表示已出现）
            if (arr[currentNum - 1] < 0) {
                // 元素重复出现，比较当前索引和最早重复位置
                if (i < earliestDuplicatePos) {
                    earliestDuplicatePos = i;
                    result = currentNum;
                }
            } else {
                // 第一次出现，标记为负数
                arr[currentNum - 1] = -arr[currentNum - 1];
            }
        }

        // 可选：恢复数组原来的数值（如果后续还要使用数组的话）
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Math.abs(arr[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] testArr = {1,4,3,5,3,2,1};
        System.out.println(findFirstDuplicateOptimized(testArr)); // 输出3
    }
}

这个方法的原理是用元素值减1作为索引，把对应位置的元素改成负数来标记该元素已经出现过，这样不用额外的存储空间，但只适用于元素范围有限的场景。

内容的提问来源于stack exchange，提问作者1KT1