唐山做网站哪家公司好,wordpress换站,线上宣传渠道,洛阳建设三轮网站文章目录 题目描述示例 1示例 2提示 解决方案题意拆解双指针算法双指针法的主要优点双指针法的使用场景举例#xff1a; 解决方案#xff1a;【双指针一次遍历】解题心得方案代码运行结果复杂度分析 结束语 移动零
题目描述
给定一个数组 nums#xff0c;编写一个函数将所… 文章目录 题目描述示例 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)
结束语
亲爱的读者感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见因此在这里鼓励您对我们的博客进行评论。您的建议和看法对我们来说非常重要这有助于我们更好地了解您的需求并提供更高质量的内容和服务。无论您是喜欢我们的博客还是对其有任何疑问或建议我们都非常期待您的留言。让我们一起互动共同进步谢谢您的支持和参与我会坚持不懈地创作并持续优化博文质量为您提供更好的阅读体验。谢谢您的阅读
