283-移动零

给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。

输入:[0,1,0,3,12] 输出:[1,3,12,0,0]

说明:

必须在原数组上操作,不能拷贝额外的数组。尽量减少操作次数。


因为只能在原数组上操作,第一想法是计算零的个数,从头到尾删除零元素,再添加。

需要注意的就是 c.erase(p) 删除迭代器p所指定的元素,返回一个指向被删除元素之后元素的迭代器,若p指向尾元素,则返回尾后迭代器,若p是尾后迭代器,则函数行为未定义。删除操作会使后面的迭代器都无效,所以要保存erase返回的迭代器。

缺点是复杂度较高,每次删除都会有大量元素的移动和拷贝,大佬肯定不能忍。

下面是最优的解法,两个指针,一个指针不停向后移动,每次遇到非零值,就与前面指针的元素进行交换。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。