【LeetCode】283. Move Zeroesを解く

問題へのリンク

問題概要

配列numsが与えられるので，配列に含まれる0を非ゼロ要素の順序を変えずに配列末尾へ移動する関数を書く．

例：

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

制約

• in-place で実装する（入力に直接変更を加える）
• 操作の回数を最小化する

考えたこと

配列numsを前から見ていき，非ゼロ出会った場合に前から順番に詰めていけばよさそう．

イメージ：
↓は非ゼロかどうかを確認する要素を指している．

最初の要素は0なので何もしない

 ↓
[0, 1, 0, 3, 12]

1は非ゼロ要素なので，１番目に詰める

    ↓
[0, 1, 0, 3, 12]
[1, 1, 0, 3, 12]

要素は0なので何もしない

       ↓
[1, 1, 0, 3, 12]

3は非ゼロ要素なので，２番目に詰める

          ↓
[1, 1, 0, 3, 12]
[1, 3, 0, 3, 12]

12は非ゼロ要素なので，３番目に詰める

             ↓
[1, 1, 0, 3, 12]
[1, 3,12, 3, 12]

このシミュレーションからどこに非ゼロ要素を詰めるのかを示すindexが必要であることが分かる．

また，所望の出力は[1,3,12,0,0]であるため0を末尾に移動する操作が必要であるが，最後の要素を見た後にindex == len(nums)になるまで0を詰めていけば所望の結果が得られる．

以上の考えに基づいた実装は以下の通りである：

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        index = 0
        
        for n in nums:
            if n != 0:
                nums[index] = n
                index += 1
        
        while(index < len(nums)):
            nums[index] = 0
            index += 1