Python数组首个重复元素索引：两段哈希表代码的差异疑问

问题背景 #

给定大小为n的数组arr[]，需要找出首个重复元素——即出现次数>1，且首次出现索引最小的元素，最终返回该元素的位置（索引+1）。我用Python哈希表实现了两段代码，在Colab中都能返回正确结果，但发现代码片段2能正常运行，代码片段1不行，同时疑惑为什么要遍历数组而非哈希表m。

代码片段 #

代码片段1 #

class Solution:
    #Function to return the position of the first repeating element.
    def firstRepeated(self,arr, n):
        m = {}
        for i in arr:
            if i not in m:
                m[i] = 1
            else:
                m[i] += 1
        for i in arr:
          if m[i] > 1:
            return arr.index(i)+1
        
        return -1

代码片段2 #

class Solution:
    #Function to return the position of the first repeating element.
    def firstRepeated(self,arr, n):
        m = {}
        for i in arr:
            if i not in arr:  # 这里有致命逻辑错误
                m[i] = 1
            else:
                m[i] += 1
        for i in arr:
          if m[i] > 1:
            return arr.index(i)+1
        
        return -1

核心问题解答 #

1. 代码片段2的错误说明 #

你说代码片段2能正常运行，大概率是写代码时的笔误——if i not in arr:这个条件完全不成立：i是从arr里遍历出来的元素，永远在数组里，所以这个条件一直为False，哈希表m会是空的，根本无法正确统计元素出现次数。正确的写法应该是if i not in m:，和代码片段1的逻辑一致。

2. 为什么遍历数组而非哈希表m #

原因很简单：哈希表的遍历顺序无法和数组元素的出现顺序完全匹配：

• 题目要找的是「首次出现索引最小的重复元素」，也就是所有重复元素里，第一次出现在数组最前面的那个。
• Python 3.7之前的字典是无序的，遍历哈希表时可能先拿到后面出现的重复元素，直接返回会得到错误结果；即使3.7及以后的字典保留插入顺序，遍历数组的逻辑也更直观，不需要依赖字典的特性，兼容性更强。

另外，你的两段代码都有性能隐患：arr.index(i)是O(n)级别的操作，嵌套在遍历数组的循环里，整体时间复杂度会变成O(n²)，遇到GFG的大测试用例肯定会超时。

3. 优化后的高效实现 #

我们可以在第一次遍历时同时记录元素的出现次数和首次出现索引，这样就能在O(n)时间内解决问题：

class Solution:
    def firstRepeated(self, arr, n):
        freq_map = {}
        first_idx_map = {}
        
        # 第一次遍历：统计次数+记录首次索引
        for idx, num in enumerate(arr):
            if num not in first_idx_map:
                first_idx_map[num] = idx
            freq_map[num] = freq_map.get(num, 0) + 1
        
        # 找所有重复元素中首次索引最小的那个
        min_first_idx = n  # 初始化为超出数组范围的值
        for num, count in freq_map.items():
            if count > 1:
                if first_idx_map[num] < min_first_idx:
                    min_first_idx = first_idx_map[num]
        
        return min_first_idx + 1 if min_first_idx != n else -1

这个版本的时间复杂度是O(n)，空间复杂度是O(n)，完全符合GFG的性能要求。

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