leetCode The first 283 topic Move zero
Given an array nums, Write a function that will 0 Move to end of array , While maintaining the relative order of non-zero elements .
Please note that , You must operate on the array in place without copying it .
Example 1:
Input : nums = [0,1,0,3,12]
Output : [1,3,12,0,0]
Example 2：‘
Input : nums = [0]
Output : [0]
Tips :
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
Advanced ： Can you minimize the number of operations completed ？
python It is very convenient to operate the list , If the algorithm is not involved , Just traverse the list , Delete the zero element , By the way, add one at the end of the list 0, The code is as follows , But the effect is very low
## python3
class Solution:
def moveZeroes(self, nums: [int]) -> None:
""" Do not return anything, modify nums in-place instead. """
for i in range(len(nums)):
if nums[i] == 0:
nums.remove(0)
nums.append(0)
Double pointers can be introduced to solve
Put the pointer i,j First point to the first element , Give Way i Keep moving back , If i It points to a non-zero element , It will be i The value pointing to the element is directly filled in j Point to , then j Pointer backward ; If i It points to a zero element , So the pointer i Just move back , and j unchanged .
When i After all traversals have been completed , from j The position begins , Fill in all zeros directly afterwards .
The pointer i.j All the way through the list , So the time complexity should be O(2n), That is, linear time complexity O(n)
The whole process only defines two pointers , Space complexity should be O(1)
It has been greatly improved in time , The effect is as follows
## python3
class Solution:
def moveZeroes(self, nums: [int]) -> None:
""" Do not return anything, modify nums in-place instead. """
if len(nums) == 0:
return
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[j] = nums[i]
j += 1
for i in range(j,len(nums)):
nums[i] = 0
