移动零OJ链接:283. 移动零 - 力扣(LeetCode)
题目:
解法(快排的思想:数组划分区间-数组分两块):
算法思路:
在本题中,我们可以用一个 dest 指针来扫描整个数组,另一个 src 指针用来记录非零数序列
的最后一个位置。根据 dest 在扫描的过程中,遇到的不同情况,分类处理,实现数组的划分。
在 dest 遍历期间,使 [0, src] 的元素全部都是非零元素, [src + 1, dest - 1] 的元素全是零。
算法流程:
a. 初始化dest=0(用来遍历数组), src = -1 (指向非零元素序列的最后⼀个位置。
因为刚开始我们不知道最后一个非零元素在什么位置,因此初始化为 -1 )
b. cur 依次往后遍历每个元素,遍历到的元素会有下面两种情况:
i. 遇到的元素是 0 , dest 直接 ++ 。因为我们的目标是让 [src + 1, dest - 1] 内的元素全都是零,因此当 dest 遇到 0 的时候,直接 ++ ,就可以让 0 在 dest - 1的位置上,从而在 [src + 1, dest - 1] 内;
ii. 遇到的元素不是 0 , src++ ,并且交换 dest 位置和 src 位置的元素,之后让 dest++ ,扫描下一个元素。
• 因为 src 指向的位置是非零元素区间的最后一个位置,如果扫描到一个新的非零元素,那么它的位置应该在 src + 1 的位置上,因此 src 先自增 1 ;
• src++ 之后,指向的元素就是 0 元素(因为非零元素区间末尾的后一个元素就是0 ),因此可以交换到 dest 所处的位置上,实现 [0, src] 的元素全部都是非零元素, [src + 1, dest - 1] 的元素全是零。
C++:
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for(int dest=0,src=-1;dest<nums.size();dest++)
{
if(nums[dest])
{
swap(nums[++src],nums[dest]);
}
}
}
};
运行结果:
复杂度分析:
时间复杂度:O(N)
空间复杂度:O(1)
PS:看到这里了,码字不易,给个一键三连鼓励一下吧!有不足或者错误之处欢迎在评论区指出!