力扣283. 移動零

文章目錄

• 1. 題目
• 2. 思路
• 3. 效果驚人

1. 題目

給定一個數組 nums，編寫一個函數将所有 0 移動到數組的末尾，同時保持非零元素的相對順序。

示例:

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:

必須在原數組上操作，不能拷貝額外的數組。
盡量減少操作次數。

 
           

2. 思路

其實題目是在不改變非0相對順序的前提下，把其它元素靠前

思路：可以先把所有非0的元素移到前面，然後将後面的位置補0。 使用指針i，指向需要插入的下标，使用指針j指向周遊的下标。周遊一遍，如果j指向的位置為0，則i不變，j++後移；如果j指向的位置不為0，則将j位置的元素值指派到i位置，然後i++。

比如：

0, 11, 3, 5, 0, 1, 4 ,0 ,2

結果是：

11，3，5，1，4，2，0，0，0

public void moveZeroes(int[] nums) {
     //i:插入位置下标 ; j:查找位置下标
     int i = 0; 
     for(int j = 0; j < nums.length; j++){
         if(nums[j] != 0){
             nums[i] = nums[j];
             i++;
         }
     }
        //将後面的位置補0
        for(int p = i; p < nums.length; p++){
            nums[p] = 0;
        }
 
    }

 
           

第一次： i=0，j=0 ,num[j]=0 ,不移動
第二次，i=0;j=1; num[j]!=0 移動，變為：
    11, 11, 3, 5, 0, 1, 4 ,0 ,2 同時i=1
第3次，i=1;j=2; num[j]!=0 移動，變為：
    11, 3, 3, 5, 0, 1, 4 ,0 ,2 同時i=2    
第4次，i=2;j=3; num[j]!=0 移動，變為：
    11, 3, 5, 5, 0, 1, 4 ,0 ,2 同時i=3  
第5次，i=3;j=4; num[j]==0 不移動  

第6次，i=3;j=5; num[j]!=0 移動，變為：
    11, 3, 5, 1, 0, 1, 4 ,0 ,2 同時i=4 
  
第7次，i=4;j=6; num[j]!=0 移動，變為：
    11, 3, 5, 1, 4, 1, 4 ,0 ,2 同時i=5 
第8次，i=5;j=7; num[j]==0 不移動
第9次，i=5;j=8; num[j]!=0 移動，變為：
    11, 3, 5, 1, 4, 2, 4 ,0 ,2 同時i=6
   到這裡，可以把6及6以後的下标全部設定為0，變為
     11, 3, 5, 1, 4, 2, 0 ,0 ,0  
           

3. 效果驚人

執行用時 :1 ms, 在所有 Java 送出中擊敗了96.12%的使用者
記憶體消耗 :41 MB, 在所有 Java 送出中擊敗了46.99%的使用者