创建一个网站要钱吗,鱼鱼cms,成都做app定制,去哪找做网站的人LeetCode 热题 100 | 283. 移动零
大家好#xff0c;今天我们来解决一道经典的算法题——移动零。这道题在LeetCode上被标记为简单难度#xff0c;要求我们将数组中的所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。下面我将详细讲解解题思路#xff0c;…LeetCode 热题 100 | 283. 移动零
大家好今天我们来解决一道经典的算法题——移动零。这道题在LeetCode上被标记为简单难度要求我们将数组中的所有 0 移动到数组的末尾同时保持非零元素的相对顺序。下面我将详细讲解解题思路并附上Python代码实现。 问题描述
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。要求原地操作不能复制数组。
示例
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]解题思路
核心思想 双指针法 使用两个指针 left 和 right其中 left 指向当前已经处理好的非零元素的末尾right 用于遍历数组。当 nums[right] 不为 0 时将其与 nums[left] 交换并将 left 右移。 原地操作 通过交换元素的方式避免使用额外的空间。 Python代码实现
def moveZeroes(nums):left 0 # 指向当前已经处理好的非零元素的末尾for right in range(len(nums)):# 如果当前元素不为0则将其移动到left位置if nums[right] ! 0:nums[left], nums[right] nums[right], nums[left]left 1# 测试示例
nums1 [0, 1, 0, 3, 12]
nums2 [0]moveZeroes(nums1)
moveZeroes(nums2)print(nums1) # 输出: [1, 3, 12, 0, 0]
print(nums2) # 输出: [0]代码解析 初始化指针 left 指针初始化为 0表示当前已经处理好的非零元素的末尾。 遍历数组 使用 right 指针遍历数组当 nums[right] 不为 0 时将其与 nums[left] 交换并将 left 右移。 交换元素 通过交换操作将非零元素移动到数组的前面同时保持相对顺序。 原地操作 直接在原数组上进行操作不需要额外的空间。 复杂度分析
时间复杂度O(n)其中 n 是数组的长度。我们只需要遍历数组一次。空间复杂度O(1)只使用了常数个额外空间。 示例运行
示例1
输入: nums [0, 1, 0, 3, 12]
输出: [1, 3, 12, 0, 0]示例2
输入: nums [0]
输出: [0]进阶减少操作次数
在基本解法中我们每次遇到非零元素都会进行一次交换操作。如果数组中没有 0这种交换是不必要的。可以通过判断 left 和 right 是否相等来减少交换次数。
优化代码
def moveZeroes_optimized(nums):left 0 # 指向当前已经处理好的非零元素的末尾for right in range(len(nums)):# 如果当前元素不为0则将其移动到left位置if nums[right] ! 0:if left ! right: # 避免不必要的交换nums[left], nums[right] nums[right], nums[left]left 1# 测试示例
nums1 [0, 1, 0, 3, 12]
nums2 [0]moveZeroes_optimized(nums1)
moveZeroes_optimized(nums2)print(nums1) # 输出: [1, 3, 12, 0, 0]
print(nums2) # 输出: [0]优化代码解析 减少交换次数 只有当 left 和 right 不相等时才进行交换操作。这样可以避免在数组中没有 0 时进行不必要的交换。 时间复杂度 仍然是 O(n)但实际运行效率更高。 总结
通过使用双指针法我们可以高效地将数组中的 0 移动到末尾同时保持非零元素的相对顺序。优化后的代码进一步减少了不必要的交换操作提高了运行效率。希望这篇题解对大家有所帮助如果有任何问题欢迎在评论区留言讨论
关注我获取更多算法题解和编程技巧
