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

难度: Easy

给你一个下标从 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 = [5,6,25,30]
输出：7
解释：数组 nums 中有 6 个强数对：(5, 5), (5, 6), (6, 6), (25, 25), (25, 30) 和 (30, 30) 。
这些强数对中的最大异或值是 25 XOR 30 = 7 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 5 XOR 6 = 3 。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= 100

Submission

运行时间: 36 ms

内存: 16.1 MB

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        ans = mask = 0
        high_bit = nums[-1].bit_length() - 1
        for i in range(high_bit, -1, -1):
            mask |= 1 << i
            new_ans = ans | (1 << i)
            d = {}
            for y in nums:
                mask_y = y & mask
                if new_ans ^ mask_y in d and d[new_ans ^ mask_y] * 2 >= y:
                    ans = new_ans
                    break
                d[mask_y] = y
        return ans

Explain

这个题解采用了基于贪心和位操作的优化策略来找到最大的异或值。首先，数组按非递减顺序排序。算法从最高位（high_bit）开始尝试构建最大的异或值。通过不断增加掩码（mask），算法尝试增加当前位的值（通过或运算），然后使用字典d来存储已经探索的y值与掩码的结果。对于每个y值，检查是否存在一个前面的x值，使得x与y的异或结果新的尝试值new_ans，并且满足强数对的条件。如果找到，则更新ans为new_ans，这意味着在当前位设置为1的情况下找到了符合条件的最大异或值。

时间复杂度: O(n * log(max(nums)))

空间复杂度: O(n)

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()  # 对数组进行排序
        ans = mask = 0
        high_bit = nums[-1].bit_length() - 1  # 计算最大值的最高位
        for i in range(high_bit, -1, -1):  # 从高位到低位检查每一位
            mask |= 1 << i  # 更新掩码，累加当前位
            new_ans = ans | (1 << i)  # 尝试将当前位设置为1以形成潜在的更大异或值
            d = {}
            for y in nums:  # 遍历每个数
                mask_y = y & mask  # 应用掩码
                if new_ans ^ mask_y in d and d[new_ans ^ mask_y] * 2 >= y:  # 检查是否存在符合强数对条件的x
                    ans = new_ans  # 更新最大异或值
                    break
                d[mask_y] = y  # 存储当前y的掩码结果
        return ans

Explore

题解中对数组进行排序的目的是为了简化查找过程，以及减少不必要的比较。排序后，数组中的元素按非递减顺序排列，这有助于在遍历和比较时更容易地处理和判断。例如，在检查强数对条件`|x - y| <= min(x, y)`时，如果y始终大于等于x，那么条件简化为`y <= 2x`，这样只需要检查x的2倍是否不小于y即可。此外，排序还有助于在使用掩码时，快速排除不可能的x，y配对，提高算法效率。

在排序后的数组中使用掩码和字典d来跟踪可能的x值（通过掩码处理的y值），算法确保在任何时候计算新的异或尝试值`new_ans`时，都能检查并验证符合强数对条件的x和y。在这种情况下，因为数组是排序的，我们知道所有在字典d中的x值都是小于或等于当前的y值的。因此，对于每个y，算法检查`new_ans`与`mask_y`的异或结果是否已经存在于字典中，并且对应的x满足`|x - y| <= min(x, y)`。由于x和y都是通过相同的掩码处理，它们之间的高位是相同的，因此主要是通过检查低位的差异来确保条件的满足。

使用掩码`mask`逐位构建可能的最大异或值的方法有效性基于异或运算的性质。异或运算（XOR）中，相同的位结果为0，不同的位结果为1。因此，为了得到最大的异或结果，我们希望结果中尽可能多的高位为1。掩码用来逐步构建这样的结果：从最高位开始，掩码逐位设置为1（从左到右），每增加一位，都尝试构建一个新的、更大的异或尝试值`new_ans`。这样做是为了在保持已有高位不变的情况下，探索在当前位设置为1时是否可以得到一个更大的异或值。通过这种方式，我们可以确保尽可能在高位获得1，从而最大化整体的异或结果。