排序一个数组如何帮助找到最小的 (Arr[i] xor Arr[j])（其中 i 不等于 j）？

Question

我最近在HackerEarth上遇到了一个问题。问题陈述要求我们在给定数组中找到min(Arr[i] xor Arr[j])。

在编辑部分，问题的作者做了这样的操作

    sort(a,a+n);
    long long ans = INT_MAX;
    for(int i=0;i<n-1;i++)
    {
        ans = min(ans, a[i]^a[i+1]);
    }

作者提到上述代码总是产生最优结果，但没有解释为什么。 我非常好奇想知道证明。

- Naveen Kumar Vunnam

---

如果它与“为什么处理排序数组比处理未排序数组快？”没有关系，我会感到惊讶。 - user4581301

等一下，也许不用了。如果数组已经排序，距离较近的元素会彼此靠近。你不必费力检查每一个元素与其他所有元素之间的距离。 - user4581301

我明白了，彼此靠近的元素总是给出比彼此远离的元素小的结果。 - Naveen Kumar Vunnam

Answer 1

好的，那么重点是，如果您有一个用二进制编码的有限数字列表Arr，则最高有效位为最大值，并且所有其他位始终为0，因此在异或时保持不变。

现在，当Arr[i]和Arr[j]是具有最长相似最高有效位链的数字对时，min(Arr[i] xor Arr[j])的最小值被获得。 如果数组已排序，则这两个数字就相邻，否则可能会通过取中间值和一侧的值来找到具有更多连续最高有效位的数字对。

请注意，符号位可能会在此处引发一些问题，我认为该方法仅适用于无符号数字。

- Laurent Jospin

---

谢谢。上述逻辑仅适用于正整数。我忘记在问题中说明了这一点。 - Naveen Kumar Vunnam