Medium

题目描述

给定一个长度为 n 的整数数组 nums，其中 nums 是范围 [1, n] 中数字的排列。

异或三元组定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 中唯一异或三元组值的数量。

示例 1：

输入：nums = [1,2]
输出：2
解释：
可能的异或三元组值为：
(0, 0, 0) → 1 XOR 1 XOR 1 = 1
(0, 0, 1) → 1 XOR 1 XOR 2 = 2
(0, 1, 1) → 1 XOR 2 XOR 2 = 1
(1, 1, 1) → 2 XOR 2 XOR 2 = 2
唯一的异或值为 {1, 2}，所以输出是 2。

示例 2：

输入：nums = [3,1,2]
输出：4
解释：
可能的异或三元组值包括：
(0, 0, 0) → 3 XOR 3 XOR 3 = 3
(0, 0, 1) → 3 XOR 3 XOR 1 = 1
(0, 0, 2) → 3 XOR 3 XOR 2 = 2
(0, 1, 2) → 3 XOR 1 XOR 2 = 0
唯一的异或值为 {0, 1, 2, 3}，所以输出是 4。

约束条件：

  • 1 <= n == nums.length <= 10^5
  • 1 <= nums[i] <= n
  • nums 是从 1 到 n 的整数排列。

提示：

  • 使用给定数字能获得的最大值和最小值是什么？
  • 我们能生成该范围内的所有数字吗？
  • 对于 n >= 3，我们可以获得 [0, 2^(msb(n) + 1) - 1] 范围内的所有数字，其中 msb(n) 是 n 的二进制表示中最高有效位的索引。需要单独处理 n <= 2 的情况。

解题思路

这道题的关键在于理解异或运算的性质和数学规律。

核心思路：

  1. 暴力解法思路：枚举所有满足 i <= j <= k 的三元组，计算异或值并去重。时间复杂度为 O(n³)。

  2. 数学规律优化：根据题目提示，当数组是 [1, n] 的排列时，异或三元组能产生的值有规律性：

    • 对于 n = 1：只能产生 1
    • 对于 n = 2：能产生 {1, 2}
    • 对于 n ≥ 3：能产生 [0, 2^(msb(n)+1) - 1] 范围内的所有整数

  3. 最优解法：直接根据数学规律计算结果，无需枚举：

    • 找到 n 的最高有效位（MSB）
    • 计算 2^(MSB+1) 的值
    • 特殊处理 n ≤ 2 的情况

推荐解法：数学规律解法，时间复杂度 O(1)，空间复杂度 O(1)。

这种方法利用了排列数组的特殊性质，通过异或运算的组合性，可以构造出连续范围内的所有值。

代码实现

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int n = nums.size();
        
        // 特殊情况处理
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // 找到n的最高有效位
        int msb = 0;
        int temp = n;
        while (temp > 1) {
            temp >>= 1;
            msb++;
        }
        
        // 返回 2^(msb+1)
        return 1 << (msb + 1);
    }
};

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 特殊情况处理
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        # 找到n的最高有效位
        msb = n.bit_length() - 1
        
        # 返回 2^(msb+1)
        return 1 << (msb + 1)

public class Solution {
    public int UniqueXorTriplets(int[] nums) {
        int n = nums.Length;
        
        // 特殊情况处理
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // 找到n的最高有效位
        int msb = 0;
        int temp = n;
        while (temp > 1) {
            temp >>= 1;
            msb++;
        }
        
        // 返回 2^(msb+1)
        return 1 << (msb + 1);
    }
}

var uniqueXorTriplets = function(nums) {
    const n = nums.length;
    const xorValues = new Set();
    
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            for (let k = j; k < n; k++) {
                xorValues.add(nums[i] ^ nums[j] ^ nums[k]);
            }
        }
    }
    
    return xorValues.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学规律解法
时间复杂度O(log n)
空间复杂度O(1)

说明：

  • 时间复杂度：O(log n)，主要用于计算最高有效位
  • 空间复杂度：O(1)，只使用常数额外空间