https://leetcode.com/problems/move-zeroes/
给定一个数组,将其所有为0的元素移到数组后面去,同时保持非零元素的相对位置不变
要求:不能新建一个数组空间;使得操作尽可能少
分析:
方法一:快慢指针
快指针在前面判断该数是否是0,慢指针在后面定位快指针找到的非零数应该放到哪个位置;等到快指针遍历完整个数组后,再把0从慢指针的位置开始逐一补上去
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int insertposition = 0;
for(int i=0; i < nums.size(); ++i)
{
if(nums[i]!=0)
{
nums[insertposition++] = nums[i];
}
}
while(insertposition < nums.size())
{
nums[insertposition++] = 0;
}
}
法一 对于 000001 这样的数组在最后面仍然需要做多次赋值0的操作,这是可以避免的,融过将0和非零元素进行调换,这样子后面就不用赋值了;
结果
Runtime: 12 ms, faster than 94.67% of C++ online submissions for Move Zeroes.
Memory Usage: 7.2 MB, less than 100.00% of C++ online submissions for Move Zeroes.
Next challenges
法二
这里同样使用快慢指针,但是保证慢指针和快指针之间的数字为0,慢指针之前的数字为非0;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int lastnon_zero = 0;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i]!=0)
{
swap(nums[lastnon_zero++], nums[i]);
}
}
}
};
Runtime: 12 ms, faster than 94.67% of C++ online submissions for Move Zeroes.
Memory Usage: 7.2 MB, less than 100.00% of C++ online submissions for Move Zeroes.
Next challenges
不过可以看到,时间并没减少,法一是赋值操作;但后面法二多了swap对调操作
原文链接: https://www.cnblogs.com/qiulinzhang/p/12639993.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/340124
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!