[Leetcode] 283. Move Zeros

21.11.22 Solved at re-trial

Problem

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:

Input: nums = [0]
Output: [0]

Solution

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

zIdx가 항상 0에서 n으로 linear하게 증가하고, idx도 마찬가지이다. 따라서 시간 복잡도는 O(2n)==O(n)이다.
간단한 알고리즘이지만 투포인터가 익숙하지 않아서인지 처음에는 안 풀렸다. 아이디어가 부족했다.

Best Solution

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

https://leetcode.com/problems/move-zeroes/discuss/208755/Python-solution
단순하게 j로 처음부터 끝까지 iterate한다. 현재까지 완성된 배열의 인덱스를 i로 trace한다. i는 현재 보고있는 elem이 0이 아닐 때만 증가한다.
퀵소트랑 비슷하다.