代理网站备案,2345网址导航怎么彻底删掉,网站常用插件,免费链接生成器难度#xff1a;简单题
题目
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。
思路#xff1a;
一开始想#xff0c;从前往后遍历简单题
题目
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
思路
一开始想从前往后遍历遇到0就挪到最后。类似于冒泡的思想但是这样做的话时间复杂度可能是 三次方。
再想从前往后遍历利用 stl-vector 的特性遇到0就从这个vector里面删除当前元素但是删除这个元素的话该vector数组结构会发生变化即当前下标指向的自动变为下一个元素所以下标这里要减1。
代码
class Solution {
public:void moveZeroes(vectorint nums) {// 要保持非零元素的相对顺序不能排序// 依次遍历遇到0元素则用冒泡排序的思想挪到最后 时间复杂度 三次方// 思路依次遍历如果遇到0则从vector中删掉该元素并记录删了几个最后添上去// 遍历时删元素会不会使数组下标发生变化会使数组结构发生变化int i 0;int n 0; // 记录删掉了几个0for(i 0; i nums.size(); i){if(nums[i] 0){nums.erase(nums.begin()i);n;i--; // 删掉当前元素数组会立即发生变化}}// 删了几个元素后面补几个0 for(i 0; i n; i){nums.push_back(0);}}
};
运行结果 好吧看了一下官方双指针代码它的效果要好一点。。 class Solution {
public:void moveZeroes(vectorint nums) {int left 0, right 0;int n nums.size();while(right n){if(nums[right]){swap(nums[left], nums[right]);left;}right;}}
}; 它的思路
