在比较列表中的元素时，如何从O(n^2)高效迭代，提高时间复杂度？

Question

我有一个列表，我想将列表中的每个元素相互比较。我知道我们可以使用嵌套循环来做到这一点，但时间复杂度是 O(n^2)。是否有任何选项可以提高时间复杂度并提高比较效率？

例如：

我有一个列表，我想在其中找出每个元素之间的数字差异。考虑一个列表 array=[100,110,010,011,100] ，我试图找出每个整数之间的数字差异。 array[0] 与 array[4]（即 100 和 100）相同，而 array[0] 有 1 个数字不同于 array[1]（即 100 和 110），而 array[0] 有 3 个数字是不同于 array[3]（即 100 和 011）。假设相似整数被定义为具有相同或数字差异仅为 1 的整数，我想 return 一个列表作为输出，其中每个元素表示具有相似数字的整数（即数字差异 <= 1).

对于输入列表array=[100,110,010,011,100]，我的预期输出应该是[2,3, 2,1,2]。在输出列表中，output[0] 表示 array[0] 类似于 array[1] 和 array[4] （即类似于 100 ，我们在列表中还有 2 个其他整数 110,100）

这是我的代码，虽然效率很低 O(n^2):

def diff(a,b):
    difference= [i for i in range(len(a)) if a[i]!=b[i]]
    return len(difference)

def find_similarity_int(array):
    # write your code in Python 3.6
    res=[0]*len(array)
    string=[]
    for n in array:
        string.append(str(n))
    for i in range(0,len(string)):
        for j in range(i+1,len(string)):
            count=diff(string[i],string[j])
            if(count<=1):
                res[i]=res[i]+1
                res[j]=res[j]+1

    return res

input_list=['100','110','010','011','100']
output=find_similarity_int(input_list)
print("The similarity metrics for the given list is : ",output)

输出：

The similarity metrics for the given list is : [2, 3, 2, 1, 2]

谁能建议一种有效的比较方法，最好只有一个循环？谢谢！

Answer 1

如果值仅为二进制数字，您可以使用多重集（集合中的计数器）获得 O(nxm) 解（其中 m 是值的宽度）。使用多重集中的值计数，添加对应于每个数字中恰好一位变化的项目计数（加上重复的数量）：

from collections import Counter
def simCount(L):
    counts = Counter(L)  # multiset of distinct values / count
    result = []
    for n in L:
        r = counts[n]-1                              # duplicates
        for i,b in enumerate(n):                     # 1 bit changes
            r += counts[n[:i]+"01"[b=="0"]+n[i+1:]]  # count others
        result.append(r)                             # sum of similars
    return result

输出：

A = ['100','110','010','011','100']

print(simCount(A)) # [2, 3, 2, 1, 2]

为避免对每个项目进行字符串操作，您可以将它们转换为整数并使用按位运算符进行 1 位更改：

from collections import Counter
def simCount(L):
    bits   = [1<<i for i in range(len(L[0]))] # bit masks
    L      = [int(n,2) for n in L]            # numeric values
    counts = Counter(L)                       # multiset n:count
    result = []
    for n in L:
        result.append(counts[n]-1)            # duplicates
        for b in bits:                        # 1 bit changes
            result[-1] += counts[b^n]         # sum similars
    return result

A = ['100','110','010','011','100']

print(simCount(A)) # [2, 3, 2, 1, 2]

在比较列表中的元素时，如何从O(n^2)高效迭代，提高时间复杂度？

When making comparison between the elements in a list, how to efficiently iterate and improve the time complexity from O(n^2)?

python

arrays

list

data-structures

python-3.x