给定一个数组，创建一个数组数组的有效方法是什么，其中每个子数组的索引与给定数组中的值相等

Question

假设我有一个大小为n的数组，其中有一些浮点值。我想创建一个包含子数组的新数组，其中每个子数组都具有原始数组中具有相等值的所有元素的索引。例如，给定一个数组givenArray=[50,20,50,20,40]，答案将是resultArray=[0,2]，[1,3]，[4]

蛮力方法是在原始数组上迭代，在每次迭代中，在结果数组上迭代，将值与每个子数组中的第一个值进行比较；如果等于它，则在此处添加其索引。如果不等于任何子数组的第一个值，则创建一个新的子数组并将其索引放在那里。python中的代码类似于：

resultArray=[]
for i in range(0,len(givenArray)):
    flag=0
    for j in range(0,len(resultArray)):
        if(givenArray[i]==givenArray[resultArray[j][0]]):
            resultArray[j].append(i)
            flag=1
    if(flag==0):
        resultArray.append([i])

此解决方案的复杂性为O（n^2）。这能在更复杂的情况下实现吗？怎样非常感谢您的想法和python代码！提前多谢

阿里

Answer 1

可以使用defaultdict和enumerate在线性时间内执行此操作：

from collections import defaultdict

result = defaultdict(list)

for i, n in enumerate(givenArray):
    result[n].append(i)
# {50: [0, 2], 20: [1, 3], 40: [4]}

result = [*result.values()]
# [[0, 2], [1, 3], [4]]

但是请注意，您的示例有int个值，而不是floatfloat作为字典键的性能较差，因为它们可能会受到舍入或精度错误的影响，特别是当它们是某种计算的结果时

Answer 2

@schwobaseggl用dict给出的答案可能是最好的，但为了完整起见，这里有一个使用groupby的解决方案

此解决方案按值的递增顺序返回组

import operator
import itertools

def group_indices(array):
  sorted_with_indices = sorted(enumerate(array), key=operator.itemgetter(1))
  groups = itertools.groupby(sorted_with_indices, key=operator.itemgetter(1))
  return [[i for i,v in g] for k,g in groups]

print(group_indices([50,20,50,20,40]))
# [[1, 3], [4], [0, 2]]

相关文件：

• builtin ^{}
• builtin ^{}
• ^{}
• ^{}