如何实现这个快速算法?
现有一个int型(32位)数组,如何快速实现任意三个数它们的前8位异或之后为0??
数组长度为20000,如要是用三重循环,速度相当慢,有没有快速算法?
[解决办法]
先转成char*或char[],每四个取一个
a^b^c=0 => a^b=c
a=array[i]: 0-> n-1
b=array[j]: i-> n-1
用hash保存c(表长度2^8,空间不大)
c=array[k]: 0-> n-1
[解决办法]
20000个数只取前8位,相当于把20000个数映射到256个值上,一定有很多重复的值
把这些重复值缩成一个数,这样实际上你所要考虑的只是256个数,而非20000
[解决办法]
一次遍历生成hash表
举个例子:
前8位 数字下标
0 1 -> 2 -> 4 -> 5
1 0 -> 3
... ...
255 ...
如果第0项有元素,找有两个以上元素的项
如果0项为空,找两个不同的项进行异或,得到的结果对应的项是否空
[解决办法]
同意楼上,用一个容量为255的hash表
[解决办法]
每个数字的前8位都设成0
任意三个数字前8位的异或都是0了
[解决办法]
a^b^c=0 => a^b=c
如果存在a=0,那么只要找到b=c(b和c对应同一项)
如果不存在a=0,那么取两个不同的a和b,异或后得到c(c≠0),找找c是否存在
[解决办法]
c(256,3) =256*255*254/(1*2*3)= 2763520, 应该能够在1秒内得到结果.