调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

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

  • |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 * 104
  • 1 <= nums[i] <= 220 - 1
通过次数
4.4K
提交次数
10.8K
通过率
40.7%


相关企业

提示 1
Sort the array, now let x <= y which means |x - y| <= min(x, y) can now be written as y - x <= x or in other words, y <= 2 * x.

提示 2
If x and y have the same number of bits, try makingy’s bits different from x if possible for each bit starting from the second most significant bit.

提示 3
If y has 1 more bit than x and y <= 2 * x use the idea about Digit DP to make y’s prefix smaller than 2 * x + 1 as well as trying to make each bit different from x using a Hashmap.

提示 4
Alternatively, use Trie data structure to find the pair with maximum XOR.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
nums =
[1,2,3,4,5]
Source