英文:

Can't increment index after swap JavaScript

问题

有一个算法问题，需要将数组中的零移动到末尾，而且不能创建新数组。这个简单的解决方法不起作用，因为它不喜欢 idx++。我感到困惑，因为我在交换之后才增加 idx。有人知道为什么会发生这种情况吗？

function zeroesToEnd(a) {
const numOfZeores = a.filter((i) => i === 0).length;
let idx = a.length - numOfZeores;
for (let i = 0; i < a.length; i++) {
let curr = a[i];

if (curr === 0) {
  let temp = a[i];
  a[i] = a[idx];
  a[idx] = temp;
  idx++; // 不允许我这样做
}

}

return a;
}

console.log(zeroesToEnd([1, 2, 0, 0, 4, 0, 5]));

<details>
<summary>英文:</summary>

Got a algorithm problem that shifts zeroes to the end of an array without making a new array. This na&#239;ve solution doesn&#39;t work because it doesn&#39;t like the idx++. I&#39;m confused because I&#39;m incrementing the idx AFTER the swap. Anyone know why this is happening?

function zeroesToEnd(a) {
const numOfZeores = a.filter((i) => i === 0).length;
let idx = a.length - numOfZeores;
for (let i = 0; i < a.length; i++) {
let curr = a[i];

if (curr === 0) {
  let temp = a[i];
  a[i] = a[idx];
  a[idx] = temp;
  idx++; //Won't let me do this
}

}

return a;
}

console.log(zeroesToEnd([1, 2, 0, 0, 4, 0, 5]));

</details>


# 答案1
**得分**: 2

问题不在于“它不喜欢 idx++”或“不让我这样做”。该 'idx++' 正在执行正常。

问题在于你陷入了一个无限循环，随着事件级联的发生：

- 当零被向前交换时，下一次迭代中会再次访问这个零；
- 同样，在第二次出现时，将执行交换，再次将该零向前移动；
- 因此，执行的交换次数将超过零的数量，因此 'idx' 将变得比预期的要大；
- 这意味着下一次交换将在数组的 'idx' 处**创建**一个新条目，使数组变得更长；
- 因此，循环条件将永远保持为真，因为 'i' 永远不会到达这个不断增长的数组的末尾。

你应该避免同一个零被移动多次，所以 'i' 不应该进入所有零必须结束的数组分区。与这个问题无关，但你应该确保在打算进行交换时，'a[idx]' **不是**零，否则交换将不会移动任何内容。

这是你的代码，带有这两个更正（用注释标记）：

<details>
<summary>英文:</summary>

The problem is not that *&quot;it doesn&#39;t like the idx++&quot;* or *&quot;doesn&#39;t let me do this&quot;*. That `idx++` is executing fine.

The problem is that you get into an infinite loop, following a cascade of events:

* When a zero is swapped *forward*, this same zero will be visited again in one of the next iterations; 
* Also this second time, a swap will be performed, moving that zero forward again;
* So the number of swaps that are executed will be more than there are zeroes, and by consequence `idx` will become greater than expected;
* This means that a next swap will **create** a new entry at `idx` in the array, making the array longer;
* By consequence the loop condition will remain true forever, as `i` never reaches the end of this growing array.

You should avoid that the same zero is moved more than once, and so `i` should never get into the partition of the array where all zeroes must end up. Not related to this problem, but you should make sure that `a[idx]` is **not** zero when you intend to make a swap, otherwise the swap is not moving anything.

Here is your code with those two corrections (marked with a comment):

&lt;!-- begin snippet: js hide: false console: true babel: false --&gt;

&lt;!-- language: lang-js --&gt;

    function zeroesToEnd(a) {
      const numZeroes = a.filter((i) =&gt; i === 0).length;
      let idx = a.length - numZeroes;
      // We only want to move zeroes that are misplaced:
      //  Don&#39;t allow i to enter the partition where all zeroes must end up
      for (let i = 0; i &lt; a.length - numZeroes; i++) { 
        let curr = a[i];

        if (curr === 0) {
          // Make sure to swap with a non-zero value
          while (a[idx] === 0) idx++; 
          let temp = a[i];
          a[i] = a[idx];
          a[idx] = temp;
          idx++;
        }
      }

      return a;
    }

    console.log(zeroesToEnd([1, 2, 0, 0, 4, 0, 5]));

&lt;!-- end snippet --&gt;



</details>