题目描述

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

示例 1：

1
2
3
输入：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：

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

解题思路

题目要求将数组从”前半部分 x + 后半部分 y”的排列方式转换为”交叉排列”的方式。换句话说，原数组的前 n 个元素是 x 组，后 n 个元素是 y 组，我们需要逐一交叉取出。

分析步骤：

  1. 数组长度为 2n，前 n 个元素 nums[0] 到 nums[n-1] 对应 x1 到 xn。
  2. 后 n 个元素 nums[n] 到 nums[2n-1] 对应 y1 到 yn。
  3. 目标顺序为：x1, y1, x2, y2, ..., xn, yn —— 即每次取一个 x，再取一个对应的 y。

算法通过循环实现：

  • 遍历索引 i 从 0 到 n-1；
  • 每次迭代中，先将 nums[i]（即 x_{i+1}）追加到结果列表；
  • 再将 nums[n + i]（即 y_{i+1}）追加到结果列表；
  • 循环结束后，结果列表恰好包含 2n 个元素，且顺序符合要求。

这种逐个追加的方式直观易懂，每个元素被访问恰好一次，结果列表的顺序自然形成交叉排列。

复杂度分析

  • 时间复杂度： O(n)，其中 n 为参数中给定的 n（数组长度的一半）。循环执行 n 次，每次进行两次 append 操作，总共 2n 次操作，与数组长度成正比。
  • 空间复杂度： O(n)，需要一个长度为 2n 的结果列表 res 来存储重排后的数组（不计返回值）。

代码

1
2
3
4
5
6
7
8
9
10
from typing import List


class Solution:
    def shuffle(self, nums: List[int], n: int) -> List[int]:
        res = []
        for i in range(n):
            res.append(nums[i])
            res.append(nums[n + i])
        return res