# LeetCode Easy 283. Move Zeroes

tags: leetcode

問題

• Explore
• Problems

アイデア

配列内の0を全て末尾の方に移せという問題です．

末尾の要素と交換をすれば良いですね．

大事なのは与えられた配列を操作することは許されていますが，新たにメモリ内に配列を作ってコピーしてはいけないという点です．

解法

• 最後に0を見つけた場所をnonzero_countとします．
• 配列を最初から走査します．
  • 0でない要素の場合
    • nonzero_countにある要素とSwapします．
    • 加えて，nonzero_countをインクリメントします．
      • nonzero_countが指す要素が0でない場合，交換は意味がありません．
      • nonzero_countが指す要素が0である場合，交換によって0が末尾近くの要素と交換されます．
      • 具体的に[1, 2, 3, 0, 4, 0, 6]などで考えると分かりやすいです．

計算量

配列の大きさを$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nonzero_count = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[i], nums[nonzero_count] = nums[nonzero_count], nums[i]
                nonzero_count += 1