文章目录
- 题目描述
- 一、两次遍历
- 二、双指针一次遍历
题目描述 给定一个数组 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题】
文章图片
时间复杂度:O(n)
空间复杂度:O(1)
二、双指针一次遍历 定义left、right指针,right从左往右移动,遇上非0元素,交换left和right对应元素,交换之后left++
(快排思想)
注意到以下性质:
- 左指针左边均为非零数;
- 右指针左边直到左指针处均为零。
void moveZeroes(vector& nums){
int n = nums.size(), left=0,right=0;
for(right;
right
文章图片
时间复杂度:O(n),其中 n为序列长度。每个位置至多被遍历两次。
空间复杂度:O(1)。
推荐阅读
- leetcode刷题记录|反转字符串——LC344题
- leetcode刷题记录|两数之和II - 输入有序数组——LC167题(中等难度)
- leetcode刷题记录|轮转数组——LeetCode198题
- Leetcode|【lc刷题】557 反转字符串中的单词 III_Day04 + 反转小结
- java|C++模板笔记
- 数据结构与算法|大数据算法题目及其解题技巧
- LeetCode编程题解法汇总|力扣解法汇总432-全 O(1) 的数据结构
- C/C++气象数据中心实战,手把手教你做工业级项目
- 蓝桥杯|蓝桥杯31天冲刺打卡(Day3)