对与最大和值 [英] Pair with Maximum AND value

问题描述

给予了非常大的整数数组中的元素可以高达10 ^ 9我怎么找到一对与最大和值。 我目前的做法是我计算所有可能的对和遍历它，找到最大的，但它是非常缓慢的。 任何其他办法？

Given a very large array of integers in which element can go upto 10^9 how do I find a pair with maximum AND value. My current approach is I calculate all possible pairs and traverse through it and find maximum, however it is very slow. Any other approach?

推荐答案

只要你能找到至少两个数相同的最显著位设置，该解决方案将涉及其中的两个。

As long as you can find at least two numbers with the same most significant bit set, the solution will involve two of them.

接着，丢弃所有其它元件和除去一切离开此最高有效位为不丢弃的数量和解决了同样的问题。直到你有剩余的只有两个数字或者有没有什么可以做的。

Next, discard all other elements and remove everything left of this MSB for the numbers not discarded and solve the same problem. Until you have just two numbers remaining or there is nothing left to do.

例如：

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

这是 O（N日志max_element）。

这篇关于对与最大和值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！