如何在 O(n) 运行时间和 O(1) 空间复杂度内重新组织数组？

Question

我是一个“空间复杂性”新手，遇到了一个问题。

假设我有一个任意整数的数组：
[1,0,4,2,1,0,5]

我如何重新排序该数组以使所有零都在一端：
[1,4,2,1,5,0,0]

...并计算非零整数的计数（在本例中：5）？

...在O(n)运行时具有O(1)空间复杂度？

我不擅长这个。
我的背景更多是环境工程而不是计算机科学，所以我通常会进行抽象思考。

我想我可以进行排序，然后计算非零整数。
然后我想当我重新排列数组时，我只能做一个每个元素的复制。
然后我想到了类似冒泡排序的方法，交换相邻元素，直到到达零的末尾。
我认为我可以通过移位数组成员的地址来节省“空间复杂度”，因为数组点指向数组，并带有其成员的偏移量。

我要么以牺牲空间复杂度为代价来增强运行时间，要么反之亦然。

解决办法是什么？

Answer 1

两指针方法将解决此任务并保持在时间和内存限制内。

首先将一个指针放置在数组的末尾，将另一个指针放置在数组的开头。然后递减结束指针，直到看到第一个非零元素。

现在是主循环：

• 如果起始指针指向0，则与结束指针指向的值交换；然后递减结束指针。
• 始终递增起始指针。
• 当起始指针大于或等于结束指针时结束。

最后，返回起始指针的位置 - 即非零元素的数量。