链接
https://leetcode-cn.com/problems/move-zeroes/
耗时
解题:9 min
题解:5 min
题意
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
说明:
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。
思路
设置两个指针,一个指针从头出发找 0,找到 0 以后,另一个指针从这个指针的下一个位置出发找第一个 非0元素,找到后互换这两个指针指向元素的位置。直到第二个指针找不到 非0元素为止。
时间复杂度:
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int pos0 = 0, pos1 = 0;
while(pos1 < n) {
while(pos0 < n && nums[pos0] != 0) pos0++;
pos1 = pos0+1;
while(pos1 < n && nums[pos1] == 0) pos1++;
if(pos1 < n) {
swap(nums[pos0], nums[pos1]);
}
}
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)