leetcode刷题记录|移动零——LeetCode283题


文章目录

  • 题目描述
  • 一、两次遍历
  • 二、双指针一次遍历

题目描述 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2: 输入: nums = [0] 输出: [0]

一、两次遍历 将全部非零元素按顺序移动到数组头部,尾部用“0”补齐。
void moveZeroes(vector& nums) { int n = nums.size(); int j = 0; for(int i=0; i

【leetcode刷题记录|移动零——LeetCode283题】leetcode刷题记录|移动零——LeetCode283题
文章图片

时间复杂度:O(n)
空间复杂度:O(1)
二、双指针一次遍历 定义left、right指针,right从左往右移动,遇上非0元素,交换left和right对应元素,交换之后left++
(快排思想)
注意到以下性质:
  1. 左指针左边均为非零数;
  2. 右指针左边直到左指针处均为零。
代码如下(示例):
void moveZeroes(vector& nums){ int n = nums.size(), left=0,right=0; for(right; right

leetcode刷题记录|移动零——LeetCode283题
文章图片

时间复杂度:O(n),其中 n为序列长度。每个位置至多被遍历两次。
空间复杂度:O(1)。

    推荐阅读