1470. 重新排列数组

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].

Return the array in the form [x1,y1,x2,y2,...,xn,yn].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3

Output: [2,3,5,4,1,7]

Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4

Output: [1,4,2,3,3,2,4,1]

Example 3:

Input: nums = [1,1,2,2], n = 2

Output: [1,2,1,2]

Constraints:

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 10^3

题目大意

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

示例 1：

输入： nums = [2,5,1,3,4,7], n = 3

输出：[2,3,5,4,1,7]

解释： 由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]

示例 2：

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

输出：[1,4,2,3,3,2,4,1]

示例 3：

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

输出：[1,2,1,2]

提示：

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 10^3

解题思路

本道题如果将 xi, yi 按要求间隔填充进一个新的结果数组，需要使用额外的空间 O(n)。

为了避免使用额外空间，可以原地修改 nums 数组。利用位操作，将两个数字编码到一个位置，然后逐一解码填充到数组的相应位置。

1. 编码阶段：使用位移和按位或操作，将两个数合并。

   • 遍历数组的前半部分（nums[0] 到 nums[n-1]）
   • 将 nums[i] 嵌入到对应后半部分的元素 nums[n + i] 的高位。
   • 前半部分的元素保持不变。

2. 解码阶段：使用位掩码和位移操作分离两个数。

   • 遍历数组的后半部分（nums[n] 到 nums[2n-1]），依次解码为两部分:
     • 使用掩码 & 1023 提取低位，即原 nums[i]。
     • 使用右移操作提取高位，即原 nums[n + i]。
   • 解码后的数填充到数组的相应位置。

注意：本方法使用了 10 位进行位操作，假设数组中的数值不超过 10 位（即最大值为 1023）。如果输入值可能超过此范围，需调整位宽或更换实现方式。

复杂度分析

• 时间复杂度: O(n)，每次遍历数组需要线性时间。
• 空间复杂度: O(1)，原地操作，无需额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number[]}
 */
var shuffle = function (nums, n) {
	// 编码阶段: 将 nums[i] 嵌入 nums[n + i] 的高位
	for (let i = 0; i < n; i++) {
		nums[n + i] |= nums[i] << 10;
	}
	// 解码阶段: 分离并重排数组
	for (let i = 0; i < n; i++) {
		const num1 = nums[n + i] >> 10; // 提取高位 nums[i]
		const num2 = nums[n + i] & 1023; // 提取低位 nums[n + i]
		// 填入解码值
		nums[2 * i] = num1;
		nums[2 * i + 1] = num2;
	}
	return nums;
};