LeetCode 1470. Shuffle the Array

题目描述

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

例如：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]。

解题思路

核心思想

这是一个数组重排问题，本质是双指针或交错填充。给定 n，我们知道：

• x 部分的元素在 nums[0] 到 nums[n-1]。
• y 部分的元素在 nums[n] 到 nums[2n-1]。

目标是将两个部分交错：x1, y1, x2, y2, ..., xn, yn。

步骤

1. 创建结果数组 ans，长度为 2n。
2. 使用指针 i 在结果数组中填充，使用指针 j 遍历 x 部分和 y 部分：
   • 每次迭代，先放入 nums[j]（来自 x 部分），然后放入 nums[j + n]（来自 y 部分）。
   • j 从 0 到 n-1。

示例

以 nums = [2,5,1,3,4,7]，n = 3 为例：

• j=0：ans[0]=nums[0]=2, ans[1]=nums[3]=3
• j=1：ans[2]=nums[1]=5, ans[3]=nums[4]=4
• j=2：ans[4]=nums[2]=1, ans[5]=nums[5]=7
• 结果：[2,3,5,4,1,7]

复杂度分析

• 时间复杂度：O(n)，一次遍历即可完成。
• 空间复杂度：O(n)（不计结果数组），结果数组长度为 2n。

代码

package code.J1470;

public class J1470 {
    public int[] shuffle(int[] nums, int n) {
        int[] ans = new int[2 * n];
        int i = 0;
        for (int j = 0; j < n; j++) {
            ans[i++] = nums[j];
            ans[i++] = nums[j + n];
        }
        return ans;
    }
}