algorithm - 最大异或与最接近的数字

Question

如果我有一个列表 L正整数，我得到另一个数字 K , 我需要在列表中找到与 K 异或的数字是最大值。

我想到了一个算法。我想用反论证来验证它的正确性。我的算法是:

• 查找 P =K的补码(1的补码)。现在在列表L中找到最接近P的数字。令这个数字为N。K和N的异或将是最大的。
• 最接近数字的数字 I在给定的一组数字中，有一个数字与 I 的差最小。

比方说，对于大于 P 的数字是不正确的在列表中L .但是数字 <=P 不正确吗？ ？

请通过提供反驳论点/建议/想法告诉我我是否正确。

Answer 1

我想你需要一个叫做 Trie 的东西.

考虑K的每一位，从高到低，当然我们可以贪婪地判断这一位的答案是否可以是1，我的意思是，首先你尽力得到1024(或更高)，然后是512，然后是256，然后......最后最后一位1。

所以首先你需要检查列表L中的某个数字是否在最高位具有与K相反的值，然后在所有选择的数字中，然后你需要在第二高位中找到与 K 值相反的数字。

现在解决方案很明显，用L构建一个Trie，从高到低确定答案的位，对应于在那棵树上的旅行。