3513. 不同 XOR 三元组的数目 I

题目描述

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

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

返回所有可能三元组 (i, j, k) 中不同的 XOR 值的数量。

排列是一个集合中所有元素的重新排列。

示例 1：

输入： nums = [1,2]

输出： 2

解释：

所有可能的 XOR 三元组值为：

(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

不同的 XOR 值为 {1, 2}，因此输出为 2。

示例 2：

输入： nums = [3,1,2]

输出： 4

解释：

可能的 XOR 三元组值包括：

(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

不同的 XOR 值为 {0, 1, 2, 3}，因此输出为 4。

提示：

1 <= n == nums.length <= 10⁵
1 <= nums[i] <= n
nums 是从 1 到 n 的整数的一个排列。

解法

方法一：位运算

由于 \(\textit{nums}\) 是 \([1, n]\) 的排列，可取的元素集合固定为 \(\{1, 2, \ldots, n\}\)。下标满足 \(i \le j \le k\)，同一下标可重复选取，因此三元组的异或值等价于从该集合中（可重复）选取三个数做异或。

当 \(n \le 2\) 时，直接枚举即可：答案分别为 \(1\)（\(n = 1\)）和 \(2\)（\(n = 2\)），即答案等于 \(n\)。

当 \(n \ge 3\) 时，可以证明：所有可能的异或结果恰好填满区间 \([0, 2^{k} - 1]\)，其中 \(2^{k}\) 是严格大于 \(n\) 的最小 \(2\) 的幂。该值也等于 \(2^{\lfloor \log_2 n \rfloor + 1}\)，在实现中可用各语言求整数位宽的函数得到：

\[ \textit{ans} = 1 \ll \textit{bitLength}(n) \]

例如 \(n = 3\) 时 \(\textit{bitLength}(3) = 2\)，答案为 \(4\)；与示例中 \(\{0, 1, 2, 3\}\) 一致。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        return n if n <= 2 else 1 << n.bit_length()

class Solution {
    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        return n <= 2 ? n : 1 << (32 - Integer.numberOfLeadingZeros(n));
    }
}

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        size_t n = nums.size();
        return n <= 2 ? n : 1 << bit_width(n);
    }
};

func uniqueXorTriplets(nums []int) int {
    n := len(nums)
    if n <= 2 {
        return n
    }
    return 1 << bits.Len(uint(n))
}

function uniqueXorTriplets(nums: number[]): number {
    const n = nums.length;
    if (n <= 2) {
        return n;
    }
    return 1 << (32 - Math.clz32(n));
}

3513. 不同 XOR 三元组的数目 I

题目描述

解法

方法一：位运算

评论