如何高效查找数组中arr(i)的后续实例？（规避经典n²循环）

这个问题我太熟了！想要避开低效的n²循环，核心思路就是用空间换时间，先做一次预处理把所有元素的位置都存起来，之后查后续位置就快得飞起～

核心思路：预处理+哈希映射 #

与其每次找后续元素都重新遍历数组（这就是n²循环的根源），不如先花O(n)的时间把数组里每个元素的所有出现索引都提前存到一个字典里。这样之后要查某个元素的后续位置，直接从字典里取对应的索引列表就行，完全不用再遍历整个数组。

具体步骤：

1. 构建索引映射表：遍历数组一次，把每个元素作为键，它所有出现的索引按顺序存入一个列表作为值。比如数组[2,3,2,5,3,2]，映射表就是{2: [0,2,5], 3: [1,4], 5: [3]}。
2. 查询后续位置：假设你已经知道某个元素的首次出现索引是first_idx，那就在该元素的索引列表里，找所有大于first_idx的索引——这些就是后续出现的位置。因为索引列表是按遍历顺序存的，本身就是有序的，还可以用二分查找快速定位第一个大于first_idx的位置，进一步提升查询效率。

代码示例（Python） #

第一步：构建索引映射表 #

def build_index_map(arr):
    index_map = {}
    for idx, num in enumerate(arr):
        if num not in index_map:
            index_map[num] = []
        index_map[num].append(idx)
    return index_map

第二步：查找后续出现位置 #

比如我们要找元素2（首次索引是0）的后续位置：

arr = [2,3,2,5,3,2]
index_map = build_index_map(arr)

target_num = 2
first_idx = 0  # 假设已经知道首次出现位置

# 拿到该元素的所有索引列表
all_indices = index_map[target_num]

# 方法1：直接遍历（适合元素出现次数少的情况）
后续位置 = [idx for idx in all_indices if idx > first_idx]
print(后续位置)  # 输出 [2,5]

# 方法2：二分查找（适合元素出现次数多的情况，更高效）
import bisect
# 找到第一个大于first_idx的位置
start_pos = bisect.bisect_right(all_indices, first_idx)
后续位置 = all_indices[start_pos:]
print(后续位置)  # 同样输出 [2,5]

为什么这个方法高效？ #

• 预处理阶段：只需要遍历数组一次，时间复杂度是O(n)，空间复杂度是O(n)（最坏情况每个元素都唯一，存所有索引）。
• 查询阶段：如果用遍历的话，时间是O(k)（k是该元素出现的次数）；如果用二分查找，时间是O(log k)，不管哪种都远优于n²的循环。
• 对比n²循环：比如数组有10000个元素全是同一个值，n²循环要做10000*10000次操作，而预处理只做10000次，查询一次只需要O(log 10000)≈14次操作，差距巨大。

额外提示 #

• 如果你的场景是需要多次查询不同元素的后续位置，这个方法的优势会更明显——只需要预处理一次，后面所有查询都是O(1)或O(log k)级别的。
• 如果数组是动态变化的（比如会新增或删除元素），那这个预处理方法就不太适用了，因为每次变化都要更新索引映射表，但如果是静态数组，这个方法绝对是最优解之一。

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