LeetCode04：移动零

4.移动零

题目

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

题解

（1）我的解法

通过循环数组的remove操作依次将0移除，移除次数为填0次数，最后在数组末尾填充相应次数的0。

1
2
3
4
5
6
7
8
9
class Solution(object):
    def moveZeroes(self, nums):
        count = 0
        while 0 in nums:
            nums.remove(0)
            count += 1
        for i in range(count):
            nums.append(0)                
        return nums

（2）官方题解

双指针

左右指针都在索引起始处，先判断右指针位置的元素是否为0，如果为0，右指针继续走一步；如果不为0，将左右指针的元素对换，左指针继续往前一步。右指针继续走一步，继续处理，直到右指针走到最末。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def moveZeroes(self, nums):
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1
        return nums

知识点

双指针法的时间与空间复杂度

时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。

空间复杂度：O(1)。只需要常数的空间存放若干变量。

双指针元素兑换

1
nums[left], nums[right] = nums[right], nums[left]

数组操作

  1. 创建数组：使用方括号 [] 来创建数组，例如 my_list = [1, 2, 3, 4, 5]。
  2. 访问元素：通过索引来访问数组中的元素，索引从 0 开始，例如 my_list[0] 返回数组的第一个元素。
  3. 切片操作：可以使用切片来获取数组中的子数组，例如 my_list[1:3] 返回索引 1 到 2 的子数组。
  4. 添加元素：使用 append() 方法向数组末尾添加新元素，例如 my_list.append(6)。
  5. 插入元素：使用 insert() 方法在指定位置插入元素，例如 my_list.insert(2, 7) 在索引 2 处插入元素 7。
  6. 删除元素：使用 remove() 方法删除指定元素，例如 my_list.remove(3) 删除元素 3。
  7. 弹出元素：使用 pop() 方法弹出指定索引的元素，例如 my_list.pop(1) 弹出索引 1 处的元素。
  8. 查找元素：使用 index() 方法查找指定元素的索引，例如 my_list.index(4) 返回元素 4 的索引。
  9. 数组长度：使用 len() 函数获取数组的长度，例如 len(my_list) 返回数组的长度。
  10. 排序数组：使用 sort() 方法对数组进行排序，例如 my_list.sort() 对数组进行升序排序。