leetCode 283 移动零

题目描述：

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

示例输入输出：

  1. 输入: [0,1,0,3,12]
  2. 输出: [1,3,12,0,0]

思路：

一次遍历

  • 利用两个指针，一个遍历数组所有数，另一个只在前一个指针遍历到非零数时改变所指位置的值并自增，最后补零

  • 参数：

    • 遍历指针num，自增指针insertPos。

  • 终止条件：

    • num遍历到数组最后一个

  • 迭代过程中做的事：

    • 检查num指向的元素是否非零

      • 非零则将insertPos所指元素赋值，值为num所指元素，并使num自增
      • 为零则遍历下一个

  • 迭代后要做的事：

    • 将insertPos向后补零

  • 复杂度分析：

    • 时间复杂度：遍历两次，O（N^2）
    • 空间复杂度：O（1）

  • 代码：

  • class Solution {
  public void moveZeroes(int[] nums) {
      if(nums == null || nums.length == 0) return;

      /*
      *@inserPos: 指向需要被替换的数字
      *@num：指向非0数字
      *for循环作用： 将每个非0的数值赋值给insPos，然后insPos++
      *特例处理：数组开头非0：insPos 赋值给自己
      */
      int insertPos = 0;
      for(int num : nums){
          if(num  != 0) nums[insertPos++] = num;
      }

      //将剩余的数补0
      while(insertPos < nums.length){
          nums[insertPos++] = 0;
      }
  }
}