当在列表中的元素之间进行比较时，如何有效地迭代并提高O(n^2)的时间复杂性

Question

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

例如：

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

对于输入列表数组=[10100110010011100]，我的预期输出应该是

[2,3,2,1,2]这是我的代码，虽然效率很低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)

输出：

给定列表的相似性度量为：[2，3，2，1，2]

有人能建议一种有效的比较方法吗，最好只使用一个循环？谢谢

Answer 1

如果值仅为二进制数字，则可以使用multiset(集合中的计数器(获得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]