查找未排序数组中的所有对,其总和可被4整除

Question

查找未排序数组中的所有对,其总和可以除以4.请建议一个比O(n*n)更好的算法

e.g.

[1,2,4,0,20,22]
k=4
[0,4]
[0,20]
[20,4]
[2,22]

Answer 1

它可以在O(n+k)这里完成,k这些对的数量(可能在其中O(n^2)).

我们的想法是创建4名列表,list0,list1,list2,list3其中list_i包含所有的元素x,使得x%4 ==i.

创建这些列表很简单,并在其中完成O(n).

一旦你有这些列表,你所要做的就是得到一个元素来自的所有对list_i,其他元素在list_((4-i)%4)(所以list0 + list0,list1 + list3,list2 + list2).这可以非常简单地完成,并且可以非常有效地生成所有对.

优化注意事项:它可以通过根据模型对数组本身进行"排序"来就地完成(非常少的额外空间),因此您将在数组本身中显示列表.

示例:(从您的列表中进行最少的修改)

array = [1,2,4,0,20,22,7]

生成列表:

list0 = [0,4,20]
list1 = [1]
list2 = [2,22]
list3 = [7]

现在,

"combine" list0 with itself: (0,4), (4,20), (0,20)
"combine" list2 with itself: (2,22)
"combine" list1 with list3: (1,7)