Easy

题目描述

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

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

你需要从 nums 中选出两个整数组成强数对，使得该数对的按位异或（XOR）值在所有强数对中最大。

返回数组 nums 所有可能的强数对中，XOR 值最大的那个值。

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

示例 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)。
这些数对中 XOR 值最大的是 3 XOR 4 = 7。

示例 2：

输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100)。
这些数对的最大 XOR 值是 10 XOR 10 = 0，因为 (100, 100) 的 XOR 值也是 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)。
这些数对的最大 XOR 值是 25 XOR 30 = 7，因为其他非零 XOR 值只有 5 XOR 6 = 3。

约束条件：

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

解题思路

解题思路

这道题要求找到所有强数对中 XOR 值最大的那个。首先我们需要理解什么是强数对：对于两个数 x 和 y，如果 |x - y| <= min(x, y)，则它们组成强数对。

思路分析

由于题目约束条件很小（数组长度最多 50，数值最多 100），我们可以使用暴力解法：

  1. 理解强数对条件：不妨设 x ≤ y，则条件 |x - y| <= min(x, y) 等价于 y - x <= x，即 y <= 2x。这意味着较大的数不能超过较小数的两倍。

  2. 暴力枚举：遍历所有可能的数对 (i, j)，检查是否满足强数对条件，如果满足则计算它们的 XOR 值并更新最大值。

  3. 优化思考：虽然可以排序后使用双指针或滑动窗口优化，但由于数据规模很小，暴力解法已经足够高效。

算法步骤

  1. 初始化最大 XOR 值为 0
  2. 双重循环遍历所有数对
  3. 对每个数对，检查是否为强数对
  4. 如果是强数对，计算 XOR 值并更新最大值
  5. 返回最大 XOR 值

时间复杂度为 O(n²)，空间复杂度为 O(1)，完全满足题目要求。

代码实现

class Solution {
public:
    int maximumStrongPairXor(vector<int>& nums) {
        int maxXor = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = nums[i], y = nums[j];
                // 检查是否为强数对：|x - y| <= min(x, y)
                if (abs(x - y) <= min(x, y)) {
                    maxXor = max(maxXor, x ^ y);
                }
            }
        }
        
        return maxXor;
    }
};

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        max_xor = 0
        n = len(nums)
        
        for i in range(n):
            for j in range(n):
                x, y = nums[i], nums[j]
                # 检查是否为强数对：|x - y| <= min(x, y)
                if abs(x - y) <= min(x, y):
                    max_xor = max(max_xor, x ^ y)
        
        return max_xor

public class Solution {
    public int MaximumStrongPairXor(int[] nums) {
        int maxXor = 0;
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = nums[i], y = nums[j];
                // 检查是否为强数对：|x - y| <= min(x, y)
                if (Math.Abs(x - y) <= Math.Min(x, y)) {
                    maxXor = Math.Max(maxXor, x ^ y);
                }
            }
        }
        
        return maxXor;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumStrongPairXor = function(nums) {
    let maxXor = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const x = nums[i], y = nums[j];
            // 检查是否为强数对：|x - y| <= min(x, y)
            if (Math.abs(x - y) <= Math.min(x, y)) {
                maxXor = Math.max(maxXor, x ^ y);
            }
        }
    }
    
    return maxXor;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历所有可能的数对
空间复杂度O(1)只使用常数额外空间

相关题目