如何高效将数组中等值元素的索引分组为子数组，复杂度优于O(n²)

优化思路 #

原暴力解法的时间开销主要来自每次遍历元素时，都需要扫描所有已有的分组来查找对应值的分组，最坏情况下时间复杂度为O(n²)。我们可以通过哈希表（字典）优化查找过程，将时间复杂度降至O(n)：

• 用字典作为中间存储，key为数组元素值，value为该值对应的所有索引列表
• 仅需单次遍历原数组：对每个索引和对应元素，检查元素是否在字典的key中
  • 若存在，直接将当前索引追加到对应value列表
  • 若不存在，以该元素为key、当前索引组成的列表为value存入字典
• 遍历完成后，按插入顺序取出字典的所有value，即为目标结果（Python 3.7+版本字典默认保留插入顺序，低版本可使用collections.OrderedDict实现相同效果）

注意事项 #

由于浮点数存在精度误差（例如0.1 + 0.2 != 0.3），如果输入数组是浮点运算生成的，建议先将浮点值按业务要求的精度做归一化处理后再作为字典的key，避免出现等值元素被分到不同组的问题。

代码示例 #

基础版本（适用于整数或精度无误差的浮点数） #

def group_indexes_by_value(givenArray):
    value_index_map = {}
    for idx, val in enumerate(givenArray):
        if val not in value_index_map:
            value_index_map[val] = []
        value_index_map[val].append(idx)
    return list(value_index_map.values())

# 测试样例
givenArray = [50, 20, 50, 20, 40]
print(group_indexes_by_value(givenArray))
# 输出：[[0, 2], [1, 3], [4]]，符合要求

带浮点精度处理版本 #

def group_indexes_by_value(givenArray, precision=4):
    value_index_map = {}
    for idx, val in enumerate(givenArray):
        # 按指定精度四舍五入，避免浮点精度问题导致分组错误
        key = round(val, precision)
        if key not in value_index_map:
            value_index_map[key] = []
        value_index_map[key].append(idx)
    return list(value_index_map.values())

复杂度说明 #

• 时间复杂度：平均O(n)，仅需一次遍历原数组，字典的查找、插入操作平均时间复杂度均为O(1)
• 空间复杂度：O(n)，需要额外存储所有元素的索引，最坏情况所有元素唯一，字典需存储n组键值对

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