「力扣」第 283 题:移动零(循环不变量)


「力扣」第 283 题:移动零

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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数。

思路:循环过程中,保持 [0, j) 这个区间中的元素非零,遍历一次就能够达到题目的要求。

时间复杂度:$O(n)$;空间复杂度:$O(1)$。

Python 代码:

class Solution:

    # 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
    # 快速排序的方法,最简单,最直接

    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        # 循环不变量保持 [0, j) 保持都非 0,
        # [j, len-1] 为 0
        # j 表示下一个非零元素的位置
        j = 0

        for i in range(len(nums)):
            # 遇到 0 放过,不是 0 的交换到前面去
            if nums[i] != 0:
                nums[j], nums[i] = nums[i], nums[j]
                j += 1


if __name__ == "__main__":
    s = Solution()
    nums = [0, 1, 0, 3, 12]
    s.moveZeroes(nums)
    print(nums)

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 355 题:设计推特(中等) 「力扣」第 355 题:设计推特(中等)
「力扣」第 355 题:设计推特 链接:https://leetcode-cn.com/problems/design-twitter 设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注
下一篇 
「力扣」的「圈子」回答:刷题刷到绝望该怎么办? 「力扣」的「圈子」回答:刷题刷到绝望该怎么办?
「力扣」的「圈子」回答:刷题刷到绝望该怎么办? 原始链接 不是大佬。我个人觉得刷题和智商没有太大的关系,刷题这件事情本身也是需要「方法」的。 我们针对算法面试准备的算法题,不是智力题,我们觉得刷题有困难,有很大一部分是心理上的因素。其实这
  目录