给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。
输入:[0,1,0,3,12] 输出:[1,3,12,0,0]
说明:
必须在原数组上操作,不能拷贝额外的数组。尽量减少操作次数。
因为只能在原数组上操作,第一想法是计算零的个数,从头到尾删除零元素,再添加。
需要注意的就是 c.erase(p) 删除迭代器p所指定的元素,返回一个指向被删除元素之后元素的迭代器,若p指向尾元素,则返回尾后迭代器,若p是尾后迭代器,则函数行为未定义。删除操作会使后面的迭代器都无效,所以要保存erase返回的迭代器。
缺点是复杂度较高,每次删除都会有大量元素的移动和拷贝,大佬肯定不能忍。
下面是最优的解法,两个指针,一个指针不停向后移动,每次遇到非零值,就与前面指针的元素进行交换。
网友评论