java - 以时间效率的方式将大数组中的所有零值移动到其前面部分

Question

你有一个整数类型值的大数组，你如何以时间效率的方式将其中的所有零值移动到数组的前面部分？

例如0,1,72,3,0,5,9,0,6,51,0,3 ---> 0,0,0,0,1,72,3,5,9,6,51,3

问候!

Answer 1

如果你想保持其他项目之间的顺序，向后循环复制所有非零项目，然后在开头填充零项目:

int source = arr.Length - 1;
int dest = arr.Length - 1;
while (source >= 0) {
  if (arr[source] != 0) {
    arr[dest--] = arr[source];
  }
  source--;
}
while (dest >= 0) arr[dest--] = 0;

如果项目的顺序不重要，您可以简单地将零项目与数组开头的项目交换:

int dest = 0;
for (int source = 0; source < arr.Length; source++) {
  if (arr[source] == 0) {
    arr[source] = arr[dest];
    arr[dest++] = 0;
  }
}

两种算法都是 O(n)。

(C# 中的示例，但它应该足够接近，因为它主要是关于算法的问题...)