与最大AND值配对

Question

与最大AND值配对

n00*_*123 1 algorithm bitwise-operators bitwise-and

给定一个非常大的整数数组,其中元素可以达到10 ^ 9,如何找到具有最大AND值的对.我目前的方法是计算所有可能的对并遍历它并找到最大值,但是它非常慢.还有其他方法吗？

Answer 1

IVl*_*lad 5

只要您能找到至少两个具有相同最高有效位集的数字,解决方案将涉及其中两个.

接下来,丢弃所有其他元素并删除此MSB剩余的所有未丢弃的数字并解决相同的问题.直到你只剩下两个数字或者没有什么可做的.

例如:

 input  || first iteration | second iteration
=================================================================
1110010 ||       x         |        x
0110111 ||   discarded     |    discarded        
1000000 ||       x         |    discarded
1000010 ||       x         |        x
=================================================================
=> solution: first and last

Run Code Online (Sandbox Code Playgroud)

这是O(n log max_element).

如果你有一堆(> 2)数字具有相同的MSB集,并且在下一步你突然没有两个数字具有相同的位设置,这意味着任何一对都是一个解决方案.(例如:`1100 1010 1001`). (2认同)

归档时间：	10 年，10 月前
查看次数：	201 次
最近记录：	9 年，5 月前