283-移动零

2019-04-19  本文已影响0人  不胖二十斤不改名zz

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

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

说明:

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


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

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

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

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

上一篇下一篇

猜你喜欢

热点阅读