我是一个’空间复杂’的新手并且遇到了问题.
假设我有一个任意整数数组：
[1,4,2,1,5]
假设我有一个任意整数数组：
[1,4,2,1,5]
我如何重新排序此数组以在一端具有所有零：
[1,5,0]
…并计算非零整数的计数(在这种情况下：5)？
…在O(n)运行时具有O(1)空间复杂度？
我不擅长这个.
我的背景是环境工程而不是计算机科学,所以我通常会抽象地思考.
我以为我可以做一个排序,然后计算非零整数.
然后我想我只能在重新排列数组时执行元素元素复制.
然后我想到了类似于冒泡的东西,切换相邻的元素,直到我用零结束.
我以为我可以通过移位数组成员的地址来节省’空间复杂度’,因为数组点指向数组,并且对其成员有偏移.
我要么以牺牲空间复杂性为代价来增强运行时,反之亦然.
解决方案是什么？
解决方法
Two-pointer approach将解决此任务并保持在时间和内存限制之内.
首先将一个指针放在末尾,另一个指针放在数组的开头.然后递减结束指针,直到看到第一个非零元素.
现在主循环：
>如果开始指针指向零,则将其与指向的值交换
由指针结束;然后递减结束指针.
>始终递增开始指针.
>当开始指针变得大于或等于结束时完成
指针.
最后,返回开始指针的位置 – 即非零元素的数量.
