HOT100 283 移动零 暴力＋双指针 双解法

题目给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意 必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:输入: nums [0]输出: [0]提示:1 nums.length 104-231 nums[i] 231 - 1进阶你能尽量减少完成的操作次数吗解法一设置一个变量 count用来表示下一个非零元素应该放置的位置。从左到右遍历数组当遇到非零元素时就将它放到 nums[count] 的位置然后 count 后移一位。由于遍历顺序是从左到右所以非零元素被写入新位置的顺序和原数组中的顺序一致因此可以保证非零元素的相对顺序不变。第一次遍历结束后nums[0] 到 nums[count - 1] 存放的就是所有非零元素且顺序正确。此时 count 也表示非零元素的个数。最后从 count 开始遍历到数组末尾将剩余位置全部置为 0完成将所有 0 移动到末尾的操作。void moveZeroes(int* nums, int numsSize) { int count 0; for (int i 0; i numsSize; i) { if (nums[i] ! 0) { if (i ! count) { // 如果数组元素均为非零则会发生很多无效赋值这行可以解决 nums[count] nums[i]; } count; } } for (int i count; i numsSize; i) { nums[i] 0; } }解法二这道题可以用双指针。slow 指向下一个非零元素应该放置的位置fast 负责遍历数组。当 fast 遇到非零元素时就将 nums[fast] 放到 nums[slow]然后 slow 后移。最后将 slow 后面的元素全部置为 0。这样可以保持非零元素的相对顺序时间复杂度是 O(n)空间复杂度是 O(1)。void moveZeroes2(int* nums,int numsSize) { int slow 0; // 用来表示下一个非零元素应该放的位置 for (int fast 0; fast numsSize; fast) { // fast 用来遍历数组 if (nums[fast] ! 0) { if (slow ! fast) { // 只有当 slow 和 fast 不同的时候才进行交换 int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp; } slow; // 移动 slow 指针到下一个位置 } } }