LeetCode 1470题：双指针法实现数组洗牌失败，求修正方案

题目描述 #

给定一个包含2n个元素的数组nums，形式为[x₁,x₂,...,xₙ,y₁,y₂,...,yₙ]。
返回形式为[x₁,y₁,x₂,y₂,...,xₙ,yₙ]的数组。

约束条件：

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

你的尝试代码 #

public int[] shuffle(int[] nums, int n) {
    int temp1 = nums[1];
    int temp2 = 0;
    int i = 1; int j = n;
    while (i < n - 1 && j < nums.length) {
        System.out.println(i + " " + j + " " + temp1 + " " + temp2 + "  " + Arrays.toString(nums));
        temp2 = temp1;
        nums[i] = nums[j];
        i++; j++;
        System.out.println(i + " " + j + " " + temp1 + " " + temp2 + " " + Arrays.toString(nums));
        temp1 = nums[i];
        nums[i] = temp2;
        i++;
        System.out.println(i + " " + j + " " + temp1 + " " + temp2 + " " + Arrays.toString(nums));
    }
    return nums;
}

问题分析 #

你的代码核心思路是原地交换元素，但存在几个关键问题导致无法通过所有测试用例：

1. 初始值与循环条件错误：
   • 初始temp1取nums[1]，当n=1时（数组长度为2），循环条件i < n-1即1 < 0不成立，直接返回原数组，不符合要求。
   • 循环条件i < n-1限制了处理范围，比如n=3时，i最多到1，无法处理第三个x元素对应的位置。
2. 元素覆盖逻辑漏洞：
   • 交换过程中，temp1和temp2的交替保存逻辑只覆盖了部分位置，后续的x元素会被提前覆盖，导致数据丢失，无法正确放回目标位置。
3. 时间复杂度认知错误：你的代码是线性遍历逻辑，实际时间复杂度为O(n)，而非你所说的O(logN)。

修改方案 #

方案1：原地修改（利用数值范围特性） #

利用数组元素<=10^3的约束（二进制不超过10位），用int类型的高位存储新值，低位保留原值，实现原地修改：

public int[] shuffle(int[] nums, int n) {
    // 将y_i的值存储到对应x_i的高位
    for (int i = n; i < 2 * n; i++) {
        nums[i - n] |= nums[i] << 10;
    }
    // 从后往前提取值，避免覆盖未处理的数据
    for (int i = n - 1; i >= 0; i--) {
        nums[2 * i + 1] = nums[i] >> 10;
        nums[2 * i] = nums[i] & 1023;
    }
    return nums;
}

方案2：创建新数组（直观易维护） #

如果不需要原地修改，最直接的方式是创建新数组按规则填充：

public int[] shuffle(int[] nums, int n) {
    int[] result = new int[2 * n];
    for (int i = 0; i < n; i++) {
        result[2 * i] = nums[i];
        result[2 * i + 1] = nums[i + n];
    }
    return result;
}

内容的提问来源于stack exchange，提问作者Abhishek Kumar Sharma