283. 移动零
283. 移动零
题目
Given an integer array nums
, move all 0
's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
Constraints:
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
Follow up: Could you minimize the total number of operations done?
题目大意
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示 :
1 <= nums.length <= 10^4
-231 <= nums[i] <= 231 - 1
进阶: 你能尽量减少完成的操作次数吗?
解题思路
- 使用一个变量
zeroCount
来记录已经遍历过的0
的数量。 - 遍历数组时,对于每个非零元素,将其与当前索引减去
zeroCount
的位置交换。- 如果当前元素是
0
,增加zeroCount
。 - 如果当前元素是非零,用解构赋值将当前元素和应该放置的位置交换,计算方式为
i - zeroCount
。
- 如果当前元素是
- 遍历完成后,所有的非零元素会被移到数组前部,而
0
会集中到数组末尾。
复杂度分析
- 时间复杂度:
O(n)
,遍历整个数组一次。 - 空间复杂度:
O(1)
,使用常量级额外空间。
代码
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function (nums) {
let zeroCount = 0; // 记录遇到的 0 的数量
for (let i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
// 如果是 0,计数器加一
zeroCount++;
} else {
// 如果是非零元素,与它应该在的位置交换
[nums[i - zeroCount], nums[i]] = [nums[i], nums[i - zeroCount]];
}
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
27 | 移除元素 | [✓] | 数组 双指针 | 🟢 | 🀄️ 🔗 |
2460 | 对数组执行操作 | 数组 双指针 模拟 | 🟢 | 🀄️ 🔗 |