leetcode 283

283问题描述:
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数

# 方法1:时间复杂度O(n)，空间复杂度O(n)
class Solution: 
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        nonzero = []
        for i in range(len(nums)):
            if nums[i]:
                nonzero.append(nums[i])
        for i in range(len(nonzero)):
            nums[i] = nonzero[i]
        for i in range(len(nonzero), len(nums)):
            nums[i] = 0

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

# 方法2：时间复杂度O(n)，空间复杂度O(1)。非零覆盖
class Solution: 
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[k] = nums[i]
                k += 1
        for j in range(k, len(nums)):
            nums[j] = 0
        return nums

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

# 方法3：时间复杂度O(n)，空间复杂度O(1)。交换思想
class Solution: 
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[k], nums[i] = nums[i], nums[k]
                k += 1
        return nums

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

# 方法4：改进3，如果数组全部非零，相当自己和自己交换，所以加一个i != k 的条件
class Solution: 
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                if i != k:
                    nums[k], nums[i] = nums[i], nums[k]
                    k += 1
                else:
                    k += 1
        return nums


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

文章来源: blog.csdn.net，作者：weixin_43178406，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_43178406/article/details/86596367