随机排列数组 - LeetCode 问题。 2 指针逼近失败

Question

我正在尝试解决LeetCode问题1470。打乱数组:

给定数组

nums

，由

2n

形式的元素组成。以

[x1,x2,...,xn,y1,y2,...,yn]

的形式返回数组。

限制：

[x1,y1,x2,y2,...,xn,yn]
1 <= n <= 500
nums.length == 2n

这是我在Java中的尝试：

1 <= nums[i] <= 10^3

我尝试了这个解决方案，使其花费了 O(logN) 时间。它对 50% 的测试用例有效，但对其余的测试用例无效。我想这里需要一些修改。我猜没有人用过这种方法。

需要进行哪些修改才能使此方法发挥作用？

Answer 1

当循环在

•     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;
      }

  时退出时，

  i >= n - 1

  中最多只能写入

  nums[0]

  的值，而

  nums[n]

  的元素最多为

  nums

  。

您使用
• nums[2*n-1]

  和

  temp1

  实现的逻辑意味着，对于更大的输入大小，甚至对于

  temp2

  ，

  i

  中的值将设置为

  nums[i]

  的

  nums[i-2]

  的值。当

  i >= 4

  为 4 时这是正确的，但当

  i

  更大时它不再正确。

有很多方法可以做到这一点，但如果为结果创建一个新数组并保持输入不变，事情就会变得容易得多。比如这样：

i

就地

要就地执行此操作，无需分配另一个相同大小的数组，您可以遵循

cycles

。我们可以想象有向图，其边将任意索引与第二个索引连接起来，而第二个索引的源值需要移动到第一个索引。输入数组中的第一个和最后一个元素表示该图中具有自身边缘的节点（它们是循环）。其他节点是（更大的）循环的一部分。我们将遵循这些循环，并在每个循环中将值旋转一步。 为了避免多次遵循相同的循环，您需要以某种方式将条目标记为已访问。您引用的代码挑战确保输入值全部严格为正，因此您可以使用符号位来存储访问过的标记并在完成后再次将其删除。

以下是该想法的可能实现：

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