【LeetCode刷题笔记(4)】【Python】【移动零】【简单】

2023-12-14 23:37:09

移动零

题目描述

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

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

示例 1

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

示例 2

  • 输入: nums = [0]
  • 输出: [0]

提示

  1. 1 <= nums.length <= 104
  2. -231 <= nums[i] <= 231 - 1

解决方案

题意拆解

根据题意,如果要在在不复制数组的情况下解决这个问题,==> 需要一个满足O(1)空间复杂度的算法,并且适合解决数组/列表数据结构的问题 ==> 自然想到双指针算法

双指针算法

双指针法是一种常用的算法思想,用于解决数组和链表等数据结构的问题。它的基本思想是使用两个指针(不一定真是指针,能存储相应元素的位置/索引就行)分别标记两个位置/索引,然后通过指针所指元素的性质对数组进行修改,同时指针进行移动完成目标的方法。

双指针法的主要优点

  1. 时间复杂度为O(n):双指针法通常可以在一次遍历中解决问题,因此时间复杂度为O(n)。
  2. 空间复杂度为O(1):双指针法通常只需要常数级别的额外空间,因此空间复杂度为O(1)。

双指针法的使用场景举例:

  1. 数组或链表操作:双指针法可以用于在数组或链表中查找、删除、插入等操作。
  2. 区间问题:双指针法可以用于解决区间相关的问题,如查找区间内的最大值、最小值等。
  3. 排序问题:双指针法可以用于快速排序、归并排序等排序算法中,提高算法的效率。

解决方案:【双指针+一次遍历】

我们可以定义两个指针leftright,其中:

  • 左指针left:标记当前非零元素应该放置的位置
  • 右指针right:标记当前遍历到的位置。

当我们通过右指针的移动遍历数组元素时,

  • 如果当前元素不为0,则将其与left位置的元素交换,并将leftright都向后移动一位。
    • 指针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)

结束语

  • 亲爱的读者,感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见,因此在这里鼓励您对我们的博客进行评论。
  • 您的建议和看法对我们来说非常重要,这有助于我们更好地了解您的需求,并提供更高质量的内容和服务。
  • 无论您是喜欢我们的博客还是对其有任何疑问或建议,我们都非常期待您的留言。让我们一起互动,共同进步!谢谢您的支持和参与!
  • 我会坚持不懈地创作,并持续优化博文质量,为您提供更好的阅读体验。
  • 谢谢您的阅读!

文章来源:https://blog.csdn.net/qq_41813454/article/details/134995995
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。