Java作业：查找数组中值等于出现次数元素的最优解法咨询

现有实现的复杂度基线 #

你当前写的双遍历+HashMap计数方案，已经达到了O(n)的时间复杂度基线——这类问题没有办法在小于O(n)的时间内解决，因为必须完整统计每个元素的出现频次，绕不开全量数组遍历的环节。
这个实现的空间复杂度是O(k)，其中k是数组内不重复元素的个数，已经属于通用场景下的合格解法。

可优化方向与最优方案选择 #

通用无取值约束场景的最优实现 #

当题目没有限制数组元素的取值范围时，HashMap方案已经是理论最优，仅存在常数项的优化空间：

• 原代码第二趟遍历原数组的逻辑存在无效开销：当数组存在大量重复元素时，你需要反复对同一个元素的频次做重复判断，完全可以直接遍历HashMap的所有键值对，仅对不重复的元素做匹配判断，大幅压缩第二趟的遍历长度。
• 优化后的参考实现：

private static int number(int[] arr) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : arr) {
        countMap.merge(num, 1, Integer::sum);
    }
    // 直接遍历不重复元素做匹配，无需回扫原数组
    for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        if (entry.getKey().equals(entry.getValue())) {
            return entry.getKey();
        }
    }
    return -1;
}

已知取值范围场景的极致优化 #

如果题目明确数组元素为非负整数，且最大值不超过数组长度n，那么空间效率会进一步提升：

• 因为“元素值等于自身出现次数”的元素，出现次数最多不会超过数组总长度n，所以取值大于n的元素完全不可能满足匹配条件，不需要纳入统计。
• 此时可以直接用定长原生数组替代HashMap做计数，省去HashMap的哈希计算、对象封装的额外开销，常数项性能远高于哈希表实现：

private static int number(int[] arr) {
    int n = arr.length;
    int[] count = new int[n + 1];
    for (int num : arr) {
        // 超出[0, n]范围的元素不可能满足匹配要求，直接跳过
        if (num >= 0 && num <= n) {
            count[num]++;
        }
    }
    for (int i = 0; i <= n; i++) {
        if (count[i] == i) {
            return i;
        }
    }
    return -1;
}

原实现的细节说明 #

你原代码的核心逻辑没有功能性问题：先完成全量频次统计再做匹配的思路是通顺的，不存在空指针风险（因为统计阶段已经把所有数组元素存入了map，第二趟取键值时一定能取到值），仅在第二趟的遍历效率上有提升空间。

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