首页 > itarticle > 283. move zeroes

283. move zeroes

admin 1月 30, 2021 0

Description

Difficulty: Easy

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

将数列中的所有 0 移到末尾，其他元素保持不变。要求原地执行

Solution

设定工作指针初始为 0 位置，设定 tail 指针指向非 0 尾部。
若工作指针指向元素为 0，则将该元素移动到 tail 位置，tail 前移一位；
若工作指针指向元素非 0，工作指针后移一位，直至工作指针遇到 tail。
实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class (object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        length = len(nums)
        tail = length - 1
        if length > 1:
            for i in xrange(length-1, 0, -1):
                if nums[i] == 0:  # if there are zeros at the end
                    tail -= 1
                else:
                    break
            j = 0
            while j < tail:
                if nums[j] == 0:
                    for k in xrange(j, tail):
                        nums[k] = nums[k+1]
                    nums[tail] = 0
                    tail -= 1
                else:
                    j += 1

最初考虑写一个递归的方法实现，每次讲末尾 0 和开头确定非 0 部分略去。但是 Python 的 list 每次切分时都会复制，因此不满足原地执行以及不使用 return 的要求。但是这个方法我很喜欢，无论如何还是附上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
def moveZeroes_main(nums):
    tail = len(nums)
    if tail > 1:
        if nums[-1] == 0:
            # tail = len(''.join([str(i) for i in nums]).rstrip('0'))
            return moveZeroes_main(nums[:-1]) + [0]
        else:
            if nums[0] == 0:
                for j in xrange(1, tail):
                    nums[j-1] = nums[j]
                nums[-1] = 0
                return moveZeroes_main(nums)
            else:
                return [nums[0]] + moveZeroes_main(nums[1:tail])
    return nums
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能