algorithm - 从列表中查找 XOR 值最小的对

Question

我正在解决一个问题，我希望对 数组中的所有整数对，然后找到 K 最小的 异或运算产生的整数。数组的大小可以是N=100000 因此 K 可以很大，但限制在 250000。

例如， 如果 N=5 且 K=4，

我们的数组是 {1 3 2 4 2}

异或运算产生的数字(1 和 3、1-2、1-4、1-2、3-2、3-4、3-2 等)

3 3 2 5 0 1 6 1 6 7

因为 K=4，我们必须打印 4 个最小的整数。 所以答案是 0 1 1 2。

由于时间限制为 2 秒且非常紧迫，因此使用蛮力方法 对所有数字进行异或会超时。我的方法是错误的，所以我需要 帮助。也许我们可以利用 K=250000 的限制并想知道它是否是 可以在不对所有整数进行异或的情况下获得 K 个最小的数字。

Answer 1

(x ^ y) == (x | y) - (x & y) >= |y - x|

按顺序对您的数字进行排序将是一个开始，因为对之间的差异将为您提供 xor 的下限，因此是何时停止寻找与 x 进行 xor 的数字的分界点。

还有一种查找 xor 小于(比方说)2 的幂的数字对的捷径，因为您只对 x <= y <= x | 感兴趣(2 ^ N - 1)。如果这不能为您提供足够的配对，请增加 N 并重试。

编辑:您当然可以通过使用 x | 排除您已经找到的 xor 小于 2 的前次幂的数字对。 (2 ^ (N - 1) - 1) < y <= x | (2 ^ N) - 1.

示例基于(排序)[1, 2, 2, 3, 4]

首先寻找 xor 小于 1 的数字对:对于每个数字 x，搜索后续数字 y = x。这给出了 {2, 2}。

如果您需要不止一对，请查找 xor 小于 2 但不小于 1 的数字对:对于每个数字 x，搜索数字 x < y <= x | 1. 这给出 {2, 3}(两次)。

请注意，最终的异或值并未完全排序，但每批都严格小于前一批。

如果您需要更多，请查找 xor 小于 4 但不小于 2 的数字对:对于每个数字 x，搜索数字 x | 1 < y <= x | 3. 这给出 {1, 2} (两次)； {1, 3}。

如果您需要更多，请查找 xor 小于 8 但不小于 4 的数字对:对于每个数字 x，搜索数字 x | 3 < y <= x | 7. 这给出 {1, 4}; {2, 4}(两次)； {3, 4}。