将0移到数组末尾 [英] Move 0's to end of array

问题描述

我需要将数组中的所有0移到数组的末尾.

I need to move all 0's in an array to the end of the array.

例如:[1、10、0、5、7]应产生[1、10、5、7、0].

Example: [1, 10, 0, 5, 7] should result in [1, 10, 5, 7, 0].

我愿意进行反向循环或常规循环.

I am open to doing a reverse loop or a regular loop.

我无法创建新阵列.

这是我到目前为止所拥有的:

Here is what I have so far:

for (int i = arr.length; i <= 0; --i) {
    if (arr[i] != 0) {
        arr[i] = arr.length - 1;
    }
}

谢谢！

推荐答案

SIZE(n)，其中n = arr.size，保留顺序:

创建一个与您要从中删除0的初始数组大小相同的数组.遍历原始数组，并将每个元素添加到新数组(如果它不为0).遇到0时，对其进行计数.现在，当您到达第一个数组的末尾时，只需将计数的0数添加到数组的末尾即可.而且，甚至更简单，因为Java将数组初始化为0，所以您可以忘记在末尾添加零.

SIZE(n) where n = arr.size, retain ordering:

Create an array that is the same size as the initial array you need to remove 0s from. Iterate over the original array and add each element to the new array provided it is not 0. When you encounter a 0, count it. Now, when you've reached the end of the first array, simply add the counted number of 0s to the end of the array. And, even simpler, since Java initializes arrays to 0, you can forget about adding the zeroes at the end.

修改

由于您添加了无法创建新数组的其他约束，因此我们需要采取与我上面建议的方法稍有不同的方法.

Since you have added the additional constraint of not being able to create a new array, we need to take a slightly different approach than the one I've suggested above.

我假设数组需要保持与0移到末尾之前相同的顺序.如果不是这种情况，那么还有另一个简单的解决方案，如Brads答案中所述:初始化最后一个零"索引到数组的最后一个元素，然后向后迭代，将所有零与最后一个零的索引递减交换，每次都递减您执行交换或看到为零.

I assume the array needs to remain in the same order as it was before the 0s were moved to the end. If this is not the case there is another trivial solution as detailed in Brads answer: initialize a "last zero" index to the last element of the array and then iterate backwards swapping any zeros with the index of the last zero which is decremented each time you perform a swap or see a zero.

要将0移到末尾而不复制数组并使元素保持正确的顺序，您可以完全按照我的建议进行操作，而不必复制数组，但在同一数组上保留两个索引.

To move the 0s to the end without duplicating the array and keeping the elements in the proper order, you can do exactly as I've suggested without duplicating the array but keeping two indices over the same array.

从数组的两个索引开始.如果元素不为零，则不要将其复制到新数组中，而应将其保留在原处并增加两个索引.当您达到零时，仅增加一个索引.现在，如果两个索引不相同，并且您没有看到0，则将当前元素替换为落后的索引位置(由于遇到0).在这两种情况下，只要当前元素不为0，就增加另一个索引.

Start with two indices over the array. Instead of copying the element to the new array if it is not zero, leave it where it is and increment both indices. When you reach a zero, increment only one index. Now, if the two indices are not the same, and you are not looking at a 0, swap current element the location of the index that has fallen behind (due to encountered 0s). In both cases, increment the other index provided the current element is not 0.

它看起来像这样:

int max = arr.length;
for (int i = 0, int j = 0; j < max; j++) {
  if (arr[j] != 0) {
    if (i < j) {
      swap(arr, i, j);
    }
    i++
  }
}

对此运行:

{ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 }

产量:

{ 1, 2, 3, 4, 5, 0, 0, 0, 0, 0 }

我为好奇的人制作了完全正常的版本.

这篇关于将0移到数组末尾的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！