283. 移动零(Move Zeroes)

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes/

描述

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

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

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

题解

双指针

class Solution {
    public void moveZeroes(int[] nums) {
        int lastNonZeroFoundAt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[lastNonZeroFoundAt++] = nums[i];
            }
        }
        for (int i = lastNonZeroFoundAt; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

复杂度分析

• 时间复杂度：。代码执行的总操作（数组写入）为（元素总数）。

• 空间复杂度：，只使用常量空间。

  双指针-优化版

  对于数组：[0，0，0，…，0，1]，第一种方法需要写次写0，我们可以只写一次。

  class Solution {
    public void moveZeroes(int[] nums) {
        for (int lastNonZeroFoundAt = 0, i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[lastNonZeroFoundAt];
                nums[lastNonZeroFoundAt] = nums[i];
                nums[i] = temp;
                lastNonZeroFoundAt++;
            }
        }
    }
  }

  复杂度分析

• 时间复杂度：。但是，操作是最优的。代码执行的总操作（数组写入）是非 0 元素的数量。这比上一个解决方案的复杂性（当大多数元素为 0 时）要好得多。但是，两种算法的最坏情况（当所有元素都为非 0 时）复杂性是相同的。

• 空间复杂度：，只使用了常量空间。