【LeetCode】【算法】283. 移动零

LeetCode 283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路

简单题，用两个指针解，把所有非0元素置换到数组前面，后面补充0

1. 定义一个slow指针，专门指向那些0元素，首先用for循环遍历nums数组，找到第一个0位置；
2. 如果没找到0位置，说明整个数组都不存在0元素，直接返回；
3. 如果找到了，则fast=slow+1，用for循环使fast遍历完整个nums数组，if (nums[fast]!=0)则将元素赋值给slow，即nums[slow++]=nums[fast]，这里之所以是nums[slow++]是因为如果是非0元素，肯定会不断地置换给0位置
4. 最后从slow出发，将nums后面全部填充为0

代码

class Solution {
    // 很强的解题思路，直接统计个数，不用做交换，速度上应该会有提升
    public void moveZeroes(int[] nums) {
        int slow = -1;

        // 为slow找到第一个0的位置
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0){
                slow = i;
                break;
            }
        }

        if (slow == -1) // 说明不存在非0元素
            return;

        // 非0元素填充
        int fast = slow + 1;
        for ( ; fast < nums.length; fast++){
            if (nums[fast] != 0){
                nums[slow++] = nums[fast];
            }
        }

        // 0元素填充
        if (slow != 0){
            for ( ; slow < nums.length; slow++){
                nums[slow] = 0;
            }
        }
    }
}