動機
醍醐灌頂!!
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]
Constraints:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
Follow up: Could you minimize the total number of operations done?
Sol
簡單卻深刻,當初是先想到bubble去跑
因為只有0,所以只要把有數字的往前提(用一個index去追蹤),之後就是從後面開始塞0就好
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
zeros = i = 0
for n in nums:
if n == 0:
zeros += 1
else:
nums[i] = n
i+=1
i = -1
while zeros > 0:
nums[i] = 0
i -= 1
zeros -= 1