时间戳

首页 > 解决方案 > 数组中重复元素的查找函数

python - 数组中重复元素的查找函数

问题描述

我有一个类似列表的正整数 python 对象，我想获取该列表上的哪些位置具有重复值。例如，如果输入是[0,1,1]函数应该返回[1,2]，因为值 1 是输入数组位置 1 和 2 的元素出现两次。相似地：

[0,13,13]应该返回[[1, 2]]

[0,1,2,1,3,4,2,2]应该返回[[1, 3], [2, 6, 7]]，因为1在输入数组的位置 [1, 3] 出现两次，在2位置 [2, 6, 7] 出现 3 次

[1, 2, 3]应该返回一个空数组[]

我写的是这样的：

def get_locations(labels):
    out = []
    label_set = set(labels)
    for label in list(label_set):
        temp = [i for i, j in enumerate(labels) if j == label]
        if len(temp) > 1:
            out.append(np.array(temp))

    return np.array(out)

虽然它适用于小型输入数组，但当大小增加时会变得太慢。例如，下面的代码在我的电脑上，从0.14secs什么时候n=1000到12secs什么时候飙升n = 10000

from timeit import default_timer as timer
start = timer()
n = 10000
a = np.arange(n)
b = np.append(a, a[-1]) # append the last element to the end
out = get_locations(b)
end = timer()
print(out)
print(end - start) # Time in seconds

请问我怎样才能加快这个速度？任何想法高度赞赏

标签： pythonarrayspython-3.xnumpybig-o

解决方案

您的嵌套循环会导致时间复杂度为O(n ^ 2)。您可以改为创建列表字典以将索引映射到每个标签，并仅在子列表的长度大于 1 时提取字典的子列表，这将时间复杂度降低到O(n)：

def get_locations(labels):
    positions = {}
    for index, label in enumerate(labels):
        positions.setdefault(label, []).append(index)
    return [indices for indices in positions.values() if len(indices) > 1]

这样get_locations([0, 1, 2, 1, 3, 4, 2, 2])返回：

[[1, 3], [2, 6, 7]]

推荐阅读