文章目录
- 题目描述
- 示例 1
- 示例 2
- 提示
- 解决方案
- 题意拆解
- 双指针算法
- 双指针法的主要优点
- 双指针法的使用场景举例:
- 解决方案:【双指针+一次遍历】
- 解题心得
- 方案代码
- 运行结果
- 复杂度分析
- 结束语
移动零
题目描述
给定一个数组 nums
,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意,必须在不复制数组的情况下原地对数组进行操作。
示例 1
- 输入:
nums = [0,1,0,3,12]
- 输出:
[1,3,12,0,0]
示例 2
- 输入:
nums = [0]
- 输出:
[0]
提示
- 1 <= nums.length <= 104
- -231 <= nums[i] <= 231 - 1
解决方案
题意拆解
根据题意,如果要在在不复制数组的情况下解决这个问题,==> 需要一个满足O(1)空间复杂度的算法,并且适合解决数组/列表数据结构的问题 ==> 自然想到双指针算法。
双指针算法
双指针法是一种常用的算法思想,用于解决数组和链表等数据结构的问题。它的基本思想是使用两个指针(不一定真是指针,能存储相应元素的位置/索引就行)分别标记两个位置/索引,然后通过指针所指元素的性质对数组进行修改,同时指针进行移动完成目标的方法。
双指针法的主要优点
- 时间复杂度为O(n):双指针法通常可以在一次遍历中解决问题,因此时间复杂度为O(n)。
- 空间复杂度为O(1):双指针法通常只需要常数级别的额外空间,因此空间复杂度为O(1)。
双指针法的使用场景举例:
- 数组或链表操作:双指针法可以用于在数组或链表中查找、删除、插入等操作。
- 区间问题:双指针法可以用于解决区间相关的问题,如查找区间内的最大值、最小值等。
- 排序问题:双指针法可以用于快速排序、归并排序等排序算法中,提高算法的效率。
解决方案:【双指针+一次遍历】
我们可以定义两个指针left
和right
,其中:
- 左指针
left
:标记当前非零元素应该放置的位置 - 右指针
right
:标记当前遍历到的位置。
当我们通过右指针的移动遍历数组元素时,
- 如果当前元素不为0,则将其与
left
位置的元素交换,并将left
和right
都向后移动一位。- 指针
left
向后移动一位的原因:更新下一个非零元素应该放置的位置; - 指针
right
向后移动一位的原因:遍历下一个数组元素;
- 指针
- 如果当前元素为0:
- 需要移动右指针
right
—> 遍历下一个数组元素; - 不需要移动左指针
left
—> 当前位置仍然是下一个非零元素应该放置的位置;
- 需要移动右指针
当循环结束后,所有非零元素都会被移动到数组的前面,而所有0元素则会被移动到数组的末尾。
解题心得
对左指针left
和右指针right
的具体功能有明确的认知,可以更好地帮助我们理解算法的运行逻辑。
方案代码
from typing import List
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
将数组中的所有零移动到数组的末尾,保持非零元素的相对顺序。
Args:
nums (List[int]): 待操作的数组。
Returns:
None: 该函数没有返回值,直接修改传入的数组。
"""
n = len(nums)
# left和right分别表示当前非零元素应该放置的位置和当前遍历到的位置。
left = 0 # left初始化为0,表示第一个位置是非零元素应该放置的位置。
right = 0 # right初始化为0,表示开始从数组的第一个位置遍历。
# 通过右指针的移动遍历数组
while right < n:
# 如果当前遍历到的元素不为0,则将其与left位置的元素交换,并将left和right都向后移动一位。
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
运行结果
复杂度分析
- 时间复杂度:O(N),其中 N 是数组
nums
元素的数量。- 需要遍历数组每一个元素 ===> O(N)
- 空间复杂度:O(1)
- 只需要存放若干变量 ===> O(1)
结束语
- 亲爱的读者,感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见,因此在这里鼓励您对我们的博客进行评论。
- 您的建议和看法对我们来说非常重要,这有助于我们更好地了解您的需求,并提供更高质量的内容和服务。
- 无论您是喜欢我们的博客还是对其有任何疑问或建议,我们都非常期待您的留言。让我们一起互动,共同进步!谢谢您的支持和参与!
- 我会坚持不懈地创作,并持续优化博文质量,为您提供更好的阅读体验。
- 谢谢您的阅读!