1829. 每个查询的最大异或值

🟠 🔖 位运算 数组 前缀和 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times :

Find a non-negative integer k < 2maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith query.
Remove the last element from the current array nums.

Return an array answer , whereanswer[i]is the answer to theithquery.

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation : The queries are answered as follows:
1st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation : The queries are answered as follows:
1st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

nums.length == n
1 <= n <= 10^5
1 <= maximumBit <= 20
0 <= nums[i] < 2maximumBit
nums is sorted in ascending order.

题目大意

给你一个有序数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次：

找到一个非负整数 k < 2maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果 最大化 。k 是第 i 个查询的答案。
从当前数组 nums 删除最后一个元素。

请你返回一个数组 answer ，其中 answer[i]是第 i 个查询的结果。

示例 1：

输入： nums = [0,1,1,3], maximumBit = 2
输出：[0,3,2,3]
解释： 查询的答案如下：
第一个查询：nums = [0,1,1,3]，k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。
第二个查询：nums = [0,1,1]，k = 3，因为 0 XOR 1 XOR 1 XOR 3 = 3 。
第三个查询：nums = [0,1]，k = 2，因为 0 XOR 1 XOR 2 = 3 。
第四个查询：nums = [0]，k = 3，因为 0 XOR 3 = 3 。

示例 2：

输入： nums = [2,3,4,7], maximumBit = 3
输出：[5,2,6,5]
解释： 查询的答案如下：
第一个查询：nums = [2,3,4,7]，k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
第二个查询：nums = [2,3,4]，k = 2，因为 2 XOR 3 XOR 4 XOR 2 = 7 。
第三个查询：nums = [2,3]，k = 6，因为 2 XOR 3 XOR 6 = 7 。
第四个查询：nums = [2]，k = 5，因为 2 XOR 5 = 7 。

示例 3：

输入： nums = [0,1,2,2,5,7], maximumBit = 3
输出：[4,3,6,4,6,7]

提示：

nums.length == n
1 <= n <= 10^5
1 <= maximumBit <= 20
0 <= nums[i] < 2maximumBit
nums 中的数字已经按升序排好序。

解题思路

异或的规则是：当且仅当两个输入值不同时，异或运算输出为 1，否则输出为 0，即“同为 0，异为 1”。

异或运算 ^ 具有以下特点：

自反性：对于任意整数 a，都有 a ^ a = 0。
交换性：a ^ b = b ^ a。
结合性：(a ^ b) ^ c = a ^ (b ^ c)，即异或的顺序可以调整。
自逆性：对于任意整数 a 和 b，a ^ b = c 则 a = b ^ c 和 b = a ^ c，可以通过对任意一个值进行异或操作，来还原另一个值。

在这个问题中，异或运算的关键在于：

求解总异或值 totalXor：
- 首先，对数组 nums 中所有元素执行异或操作，得到 totalXor，即 nums[0] ^ nums[1] ^ ... ^ nums[n-1]。
- totalXor 表示当前数组的整体异或值，会基于它来计算每次查询时的结果。
确定 k 的最佳值：
- 本题的目标是找到一个整数 k，使得 totalXor ^ k 的值尽可能大。
- 在二进制表示中，所有 1 的位会贡献最大的值，因此希望选择 k 使其与 totalXor 的每一位相反，即 k = (2^maximumBit - 1) ^ totalXor。
- 这里 (2^maximumBit - 1) 是一个包含 maximumBit 位数的全 1 的数。比如，maximumBit = 3 时，2^3 - 1 = 7，即二进制 111。
逐步移除元素并更新 totalXor：
- 每次查询后，都要将 nums 数组的最后一个元素从 totalXor 中移除，模拟“删除”操作。
- 由于异或的自逆性，可以通过 totalXor ^= nums[i] 来移除最后一个元素的影响（相当于从 totalXor 中减去 nums[i]）。
- 更新 totalXor 后，可以继续进行下一次查询，直到所有元素被处理完毕。

复杂度分析

时间复杂度：O(n)，因为只需遍历数组一次来计算 totalXor，并在后续操作中遍历 nums 一次。
空间复杂度：O(n)，用于存储结果数组。

代码

/**
 * @param {number[]} nums
 * @param {number} maximumBit
 * @return {number[]}
 */
var getMaximumXor = function (nums, maximumBit) {
	const maxVal = (1 << maximumBit) - 1; // 2^maximumBit - 1
	const n = nums.length;
	let totalXor = 0;
	const result = new Array(n);

	// 计算初始的 totalXor
	for (let num of nums) {
		totalXor ^= num;
	}

	// 逐步移除最后一个元素并计算结果
	for (let i = 0; i < n; i++) {
		result[i] = maxVal ^ totalXor;
		totalXor ^= nums[n - 1 - i]; // 移除最后一个元素
	}

	return result;
};

1829. 每个查询的最大异或值

# 1829. 每个查询的最大异或值

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

1829. 每个查询的最大异或值

题目

题目大意

解题思路

复杂度分析

代码

相关题目