[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이 아닐 때만 증가한다.
퀵소트랑 비슷하다.
Author And Source
이 문제에 관하여([Leetcode] 283. Move Zeros), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jong_p/Move-Zeros저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)