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

Question

您将获得一个具有Integral类型值的大数组,如何以时间效率方式将其中的所有零值移动到数组的前部？

例如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#中的例子,但它应该足够接近,因为它主要是关于算法的问题......)