Hard

题目描述

给你一个长度为 n 的整数数组 nums，其中每个元素都是非负整数。

选择 nums 的两个子序列（可以为空，允许重叠），每个子序列都保持元素的原始顺序，设：

  • X 是第一个子序列中所有元素的按位异或值。
  • Y 是第二个子序列中所有元素的按位异或值。

返回 X XOR Y 的最大可能值。

注意：空子序列的异或值为 0。

示例 1：

输入: nums = [1,2,3]
输出: 3
解释:
选择子序列：
- 第一个子序列 [2]，其异或值为 2。
- 第二个子序列 [2,3]，其异或值为 1。
然后，两个子序列的异或值 = 2 XOR 1 = 3。
这是从任意两个子序列中可以获得的最大异或值。

示例 2：

输入: nums = [5,2]
输出: 7
解释:
选择子序列：
- 第一个子序列 [5]，其异或值为 5。
- 第二个子序列 [2]，其异或值为 2。
然后，两个子序列的异或值 = 5 XOR 2 = 7。
这是从任意两个子序列中可以获得的最大异或值。

约束条件：

  • 2 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

这道题目的关键洞察是：我们需要理解什么情况下能获得最大的异或值。

首先分析问题的本质：我们要选择两个子序列，使得它们的异或值再次异或的结果最大。根据异或运算的性质，对于任意数组元素的组合，我们可以通过线性基（XOR Basis）来表示所有可能的异或组合。

核心思路：

  1. 构建线性基：将数组中所有元素加入线性基，线性基可以表示通过这些元素能组成的所有异或值
  2. 贪心求解：从线性基中贪心地选择能使结果最大的组合

线性基的构建过程：

  • 对于每个数字，从最高位开始尝试将其加入基中
  • 如果当前位在基中还没有代表元素，则将该数字作为该位的代表
  • 否则通过异或消除该位，继续处理低位

求最大异或值：

  • 从高位到低位贪心选择，如果选择某个基元素能使当前结果变大，就选择它

这种方法的正确性在于：任何两个子序列的异或值的再次异或，等价于原数组中某些元素的异或（每个元素要么不选，要么选择奇数次）。线性基恰好能表示所有这样的组合。

代码实现

class Solution {
public:
    int maxXorSubsequences(vector<int>& nums) {
        vector<int> basis(30, 0);
        
        // 构建线性基
        for (int num : nums) {
            for (int i = 29; i >= 0; i--) {
                if (!(num & (1 << i))) continue;
                
                if (!basis[i]) {
                    basis[i] = num;
                    break;
                }
                
                num ^= basis[i];
            }
        }
        
        // 贪心求最大异或值
        int result = 0;
        for (int i = 29; i >= 0; i--) {
            result = max(result, result ^ basis[i]);
        }
        
        return result;
    }
};

class Solution:
    def maxXorSubsequences(self, nums: List[int]) -> int:
        basis = [0] * 30
        
        # 构建线性基
        for num in nums:
            for i in range(29, -1, -1):
                if not (num & (1 << i)):
                    continue
                    
                if not basis[i]:
                    basis[i] = num
                    break
                    
                num ^= basis[i]
        
        # 贪心求最大异或值
        result = 0
        for i in range(29, -1, -1):
            result = max(result, result ^ basis[i])
            
        return result

public class Solution {
    public int MaxXorSubsequences(int[] nums) {
        int[] basis = new int[30];
        
        // 构建线性基
        foreach (int num in nums) {
            int current = num;
            for (int i = 29; i >= 0; i--) {
                if ((current & (1 << i)) == 0) continue;
                
                if (basis[i] == 0) {
                    basis[i] = current;
                    break;
                }
                
                current ^= basis[i];
            }
        }
        
        // 贪心求最大异或值
        int result = 0;
        for (int i = 29; i >= 0; i--) {
            result = Math.Max(result, result ^ basis[i]);
        }
        
        return result;
    }
}

var maxXorSubsequences = function(nums) {
    const basis = new Array(30).fill(0);
    
    // 构建线性基
    for (let num of nums) {
        for (let i = 29; i >= 0; i--) {
            if (!(num & (1 << i))) continue;
            
            if (!basis[i]) {
                basis[i] = num;
                break;
            }
            
            num ^= basis[i];
        }
    }
    
    // 贪心求最大异或值
    let result = 0;
    for (let i = 29; i >= 0; i--) {
        result = Math.max(result, result ^ basis[i]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n × log(max_val))
空间复杂度O(log(max_val))

其中 n 是数组长度，max_val 是数组中的最大值。由于数字最大为 10^9，所以 log(max_val) ≈ 30。