[LeetCode] 283.移动零 题解

给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。示例 1:输入:nums [0,1,0,3,12]输出:[1,3,12,0,0]示例 2:输入:nums [0]输出:[0]本题给出了C/C的代码。算法1采用快慢指针协同遍历快指针负责寻找非零元素慢指针标记当前待替换的零元素位置每找到一个非零元素便与慢指针位置交换实现非零元素前移与零元素后移的同步完成。nzero为快指针全程遍历数组负责探测非零元素idx 为慢指针始终指向当前最靠前的零元素位置。快指针遇到非零元素时与慢指针位置的元素进行交换保证非零元素前移。交换后慢指针后移指向下一个待填充的零位置快指针持续推进直至遍历结束。class Solution { public: void moveZeroes(vectorint nums) { int idx 0; int nzero 0; int temp 0; while(nzero nums.size()){ if(nums[nzero]){ //不等于0交换 temp nums[nzero]; nums[nzero] nums[idx]; nums[idx] temp; idx; //慢指针 } nzero; //快指针找非0元素 } } }; //C语言 void moveZeroes(int* nums, int numsSize) { int idx 0; for(int i 0; i numsSize; i){ if(nums[i] ! 0){ int temp nums[i]; nums[i] nums[idx]; nums[idx] temp; idx; } } }算法2先遍历数组将所有非零元素按原有顺序依次覆盖到数组前端完成非零元素的归集再对剩余未覆盖的位置统一赋值为 0实现零元素后置。使用双标记变量idx 记录下一个非零元素应放置的目标位置nzero 作为遍历指针扫描整个数组。遍历过程中若当前元素非零则将其赋值到idx指向的位置并将 idx 后移。遍历完成后所有非零元素已有序排列在数组前半段从 idx 开始到数组末尾的所有位置统一置 0。class Solution { public: void moveZeroes(vectorint nums) { int idx 0; int nzero 0; //非0元素 while(nzero nums.size()){ if(nums[nzero]){ //不等于0的值利用idx下标维护 nums[idx] nums[nzero]; } nzero; //找非0值 } while(idx nums.size()){ //非0值处理完将剩余元素置为0 nums[idx] 0; } } }; //C语言 void moveZeroes(int* nums, int numsSize) { int idx 0; for(int i 0; i numsSize; i){ if(nums[i] ! 0){ nums[idx] nums[i]; } } while(idx numsSize){ nums[idx] 0; } }两种算法时间复杂度均为 O (n)满足题目线性时间要求且均在原数组上操作空间复杂度为 O (1)。但从动图来看第一种算法并没有将所有元素进行交换而第二种算法则会将所有的元素值进行处理。所以想要尽可能减少完成操作的次数应该使用算法一。