我们有一个阵列A (say [1,2,3]).我们需要找到数组中所有整数对的XOR(^)SUM.虽然这可以轻松完成,O(n^2)但我如何才能提高解决方案的复杂性？例如对于上面的数组,A,答案是(1^2)+(1^3)+(2^3) = 6
谢谢.
int*_*jay 21
您可以将计算分开,一次执行一位.
例如,查看数组中所有数字的最右边位.假设a数字最右边是0位,b数字有1位.然后在对中,a*b它们在XOR的最右边位置将有1.这是因为有一些a*b方法可以选择一个具有0位且一个具有1位的数字.因此,这些位将有助于a*b所有异或的总和.
通常,当查看n第n位(最右边的位是第0位)时,计算有多少个数字为0(称为n)和多少有1(称为b n).对最终总和的贡献将是n*b n*2 n.您需要为每个位执行此操作并将所有这些贡献加起来.
这可以在O(kn)时间内完成,其中k是给定值中的位数.