Java – moves all zero values in a large array to the front of it in a time efficient manner

You will get a large array with integral type values. How can you move all zero values to the front of the array in a time-efficient manner?

For example, 0,1,72,3,5,9,6,51,3 - > 0,3

to greet!

Solution

If you want to maintain the order between other items, loop back through all non-zero items, and then fill in zero items at the beginning:

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;@H_404_22@ 
 
如果项目的顺序不重要,您可以简单地将零项目与数组开头的项目交换：
 
 
 
 
int dest = 0;
for (int source = 0; source < arr.Length; source++) {
  if (arr[source] == 0) {
    arr[source] = arr[dest];
    arr[dest++] = 0;
  }
}@H_404_22@ 
 
两种算法都是O(n).
 
 
(C#中的例子,但它应该足够接近,因为它主要是关于算法的问题……)