LeetCode - 283. 移动零 Java

说明:
https://leetcode-cn.com/problems/move-zeroes/

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

通过快慢指针，一次遍历，快指针正常向后遍历，慢指针指向最后一个非零的元素，找到非零元素，将非零元素赋值给慢指针的位置，将非零元素赋值为零。具体算法演进过程见swift版本：https://www.jianshu.com/p/b5bcab69913d

时间复杂度为O(n)
空间复杂度为0(1)
算法:

class Solution {
    public void moveZeroes(int[] nums) {
        // 数组元素个数小于2，无需处理
        if (nums.lenght < 2) {
            return;
        }
        // 快指针：i；慢指针：lastNonZeroIndex
        int lastNonZeroIndex = 0;
        for(int i = 0; i < nums.length; i++) {
            // 判断非零元素
            if(nums[i] != 0) {
                // 避免 i == lastNonZeroIndex 时多余的操作
                if(i > lastNonZeroIndex) {
                    // 此处可以使用快慢指针位置元素的交换，因为是和确定的元素0交换，所以可以直接赋值
                    // 将后面的非零元素赋值到前面的慢指针位置
                    nums[lastNonZeroIndex] = nums[i];
                    // 非零元素赋值为0
                    nums[i] = 0;
                }
                lastNonZeroIndex++;
            }
        }
    }
}

作者：huxq-coder
链接：https://leetcode-cn.com/problems/move-zeroes/solution/kuai-man-zhi-zhen-by-huxq-coder/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。