LeetCode 热题 100 283. 移动零

LeetCode 热题 100 | 283. 移动零

各人好，本日我们来解决一道经典的算法题——移动零。这道题在LeetCode上被标记为简单难度，要求我们将数组中的所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。下面我将详细讲解解题思绪，并附上Python代码实现。

---

问题形貌

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。要求原地操纵，不能复制数组。
示例：

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

复制代码

---

解题思绪

核心思想

• 双指针法：
  
  
  
  • 利用两个指针 left 和 right，其中 left 指向当前已经处理好的非零元素的末尾，right 用于遍历数组。
    
  • 当 nums[right] 不为 0 时，将其与 nums[left] 交换，并将 left 右移。
    
  
  
• 原地操纵：
  
  
  
  • 通过交换元素的方式，制止利用额外的空间。
    
  
  

---

Python代码实现

1. def moveZeroes(nums):
2.     left = 0  # 指向当前已经处理好的非零元素的末尾
3.     for right in range(len(nums)):
4.         # 如果当前元素不为0，则将其移动到left位置
5.         if nums[right] != 0:
6.             nums[left], nums[right] = nums[right], nums[left]
7.             left += 1
9. # 测试示例
10. nums1 = [0, 1, 0, 3, 12]
11. nums2 = [0]
13. moveZeroes(nums1)
14. moveZeroes(nums2)
16. print(nums1)  # 输出: [1, 3, 12, 0, 0]
17. print(nums2)  # 输出: [0]

复制代码

---

代码分析

• 初始化指针：
  
  
  
  • left 指针初始化为 0，表现当前已经处理好的非零元素的末尾。
    
  
  
• 遍历数组：
  
  
  
  • 利用 right 指针遍历数组，当 nums[right] 不为 0 时，将其与 nums[left] 交换，并将 left 右移。
    
  
  
• 交换元素：
  
  
  
  • 通过交换操纵，将非零元素移动到数组的前面，同时保持相对顺序。
    
  
  
• 原地操纵：
  
  
  
  • 直接在原数组上举行操纵，不需要额外的空间。
    
  
  

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次。
  
• 空间复杂度：O(1)，只利用了常数个额外空间。
  

---

示例运行

示例1

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

复制代码

示例2

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

复制代码

---

进阶：镌汰操纵次数

在根本解法中，我们每次遇到非零元素都会举行一次交换操纵。如果数组中没有 0，这种交换是不须要的。可以通过判定 left 和 right 是否相等来镌汰交换次数。
优化代码

1. def moveZeroes_optimized(nums):
2.     left = 0  # 指向当前已经处理好的非零元素的末尾
3.     for right in range(len(nums)):
4.         # 如果当前元素不为0，则将其移动到left位置
5.         if nums[right] != 0:
6.             if left != right:  # 避免不必要的交换
7.                 nums[left], nums[right] = nums[right], nums[left]
8.             left += 1
10. # 测试示例
11. nums1 = [0, 1, 0, 3, 12]
12. nums2 = [0]
14. moveZeroes_optimized(nums1)
15. moveZeroes_optimized(nums2)
17. print(nums1)  # 输出: [1, 3, 12, 0, 0]
18. print(nums2)  # 输出: [0]

复制代码

---

优化代码分析

• 镌汰交换次数：
  
  
  
  • 只有当 left 和 right 不相等时，才举行交换操纵。
    
  • 如许可以制止在数组中没有 0 时举行不须要的交换。
    
  
  
• 时间复杂度：
  
  
  
  • 仍然是 O(n)，但实际运行效率更高。
    
  
  

---

总结

通过利用双指针法，我们可以高效地将数组中的 0 移动到末尾，同时保持非零元素的相对顺序。优化后的代码进一步镌汰了不须要的交换操纵，进步了运行效率。盼望这篇题解对各人有所帮助，如果有任何问题，接待在批评区留言讨论！
关注我，获取更多算法题解和编程本领！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。