283.Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

解析:

• 想到的解法是，把array中每個非0數(shù)字都往前挪一挪，挪到哪里？可以設(shè)置一個pos指針，pos從索引0開始，遍歷數(shù)組時，把非0數(shù)字都賦值到pos位置，然后pos自增1，直到遍歷結(jié)束。這個算法時間復(fù)雜度是o(n)，但是空間復(fù)雜度不是最優(yōu)。所以還有一種解法是互換位置。以下只列出第一種解法：

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