找出强数对的最大异或值 II

难度: Hard

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

|x - y| <= min(x, y)

你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的最大异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

示例 1：

输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。

示例 2：

输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。

示例 3：

输入：nums = [500,520,2500,3000]
输出：1020
解释：数组 nums 中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。

提示：

1 <= nums.length <= 5 * 10⁴
1 <= nums[i] <= 2²⁰ - 1

Submission

运行时间: 187 ms

内存: 22.2 MB

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        x = self.highestBit(nums[-1])
        tail = n - 1
        ans = 0
        top = 0
        while x:
            for i in range(tail, -1, -1):
                num = nums[i]
                if num < top:
                    break
                lowNum = (nums[i] + 1) >> 1
                highNum = (num ^ ans ^ x) | (x - 1)
                if lowNum > highNum or highNum >= num:
                    continue
                lowNum = max(lowNum, highNum & ~(x - 1))
                if self.check(nums, 0, i - 1, lowNum, highNum):
                    ans |= x
                    tail = i
                    if top == 0:
                        top = x
                    break
            x >>= 1
        return ans

    def highestBit(self, num: int) -> int:
        num |= num >> 1
        num |= num >> 2
        num |= num >> 4
        num |= num >> 8
        num |= num >> 16
        return num - (num >> 1)

    def check(
        self, nums: List[int], left: int, right: int, lowNum: int, highNum: int
    ) -> bool:
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] < lowNum:
                left = mid + 1
            elif highNum < nums[mid]:
                right = mid - 1
            else:
                return True
        return False

Explain

此题解采用了排序和位操作的方法来寻找最大的异或值。首先，对数组进行排序以便后续的二分查找。主要的策略是从最高位开始尝试设置当前异或结果的每一位（从高到低），检查是否存在有效的强数对能够支持这一位的设置。使用一个辅助函数highestBit来确定最大数值的最高有效位。然后在此位上，从后向前遍历数组，对于每个数，确定其潜在的强数对区间，并使用二分查找在有效区间内寻找合适的强数对。若找到，则更新当前最大异或值ans并缩小后续搜索的范围。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()  # 数组排序
        n = len(nums)  # 数组长度
        x = self.highestBit(nums[-1])  # 最大值的最高位
        tail = n - 1  # 初始化尾指针
        ans = 0  # 初始化最大异或值
        top = 0  # 初始边界值
        while x:  # 从最高位向低位处理
            for i in range(tail, -1, -1):
                num = nums[i]
                if num < top:  # 若当前数字小于边界值，则跳出
                    break
                lowNum = (nums[i] + 1) >> 1  # 计算强数对的最小可能值
                highNum = (num ^ ans ^ x) | (x - 1)  # 计算强数对的最大可能值
                if lowNum > highNum or highNum >= num:  # 若不满足条件，继续
                    continue
                lowNum = max(lowNum, highNum & ~(x - 1))  # 调整最小值
                if self.check(nums, 0, i - 1, lowNum, highNum):  # 检查是否存在有效的强数对
                    ans |= x  # 更新结果
                    tail = i  # 更新尾指针
                    if top == 0:  # 更新边界值
                        top = x
                    break
            x >>= 1  # 处理下一位
        return ans

    def highestBit(self, num: int) -> int:  # 辅助函数，计算最高有效位
        num |= num >> 1
        num |= num >> 2
        num |= num >> 4
        num |= num >> 8
        num |= num >> 16
        return num - (num >> 1)

    def check(self, nums: List[int], left: int, right: int, lowNum: int, highNum: int) -> bool:  # 二分查找
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] < lowNum:
                left = mid + 1
            elif highNum < nums[mid]:
                right = mid - 1
            else:
                return True
        return False

Explore

此条件确保两数x和y的差值不超过它们中的较小者。这意味着y最多是x的两倍减一（即y <= 2x - 1），这是因为如果y大于2x-1，差值|y-x|将大于x，不满足条件。这个条件防止了差值过大，确保两数在数量级上相近，从而可以视为强数对。

在二分查找中，我们通过设置lowNum和highNum来定义搜索范围，这两个值分别代表了在当前位设置下，可能与x形成强数对的y值的最小和最大界限。通过不断调整左右边界（left和right），检查中间值mid是否在这个范围内，如果找到，则表明存在满足强数对条件的y值。

当在某位上找到满足条件的强数对时，这意味着在这一位上可以安全地将ans的相应位从0设置为1（通过与x进行或操作），因为这保证了在此位上ans不会丢失潜在的最大值。这种操作确保了每找到一个更高的有效位，ans都能尽可能大地增加，从而达到最大异或值。

更新尾指针tail的目的是缩小搜索的范围，提高效率。当在某一位找到了符合条件的强数对时，后续的搜索就可以限制在当前找到的数的位置之前，因为更高位的数已经不再可能有更大的贡献。这样做通过减少不必要的比较和搜索，加快了算法的执行速度。