Plain's Blog

休想打败我的生活🔥

  1. 1. 题目描述(官方原文)
    1. 1.1. 示例
    2. 1.2. 说明
  2. 2. 思路
    1. 2.1. 指针法
    2. 2.2. 冒泡法
  3. 3. 代码实现(Java)
  4. 4. 复杂度

题目链接:https://leetcode-cn.com/problems/move-zeroes/

题目描述(官方原文)

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

示例

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

说明

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

思路

指针法

设置指针标记元素为0的索引,通过遍历数组,判断当前元素非0时,将当前元素的值赋给指针,并将指针++,最后将指针往后的元素赋0即可

冒泡法

核心思想是冒泡排序,设置start值记录0的下标,首先遍历数组,当判断元素非0时,就把当前值赋给temp临时存储,将nums[start]赋给当前nums[i],在将temp赋给nums[start],然后start++,直到最后将0移动到最后。

代码实现(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void moveZeroes(int[] nums) {

/**
* 指针法
*/
int pos = 0;

for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[pos] = nums[i];
pos++;
}
}


for (;pos<nums.length; pos ++){
nums[pos] = 0;
}

/**
* 冒泡法
*/
for (int i = 0,start = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[start];
nums[start++] = temp;
}
}

}

复杂度

  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

本文作者 : Plain
This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接 : https://plain-dev.com/leetcode-move-zeroes/

本文最后更新于 天前,文中所描述的信息可能已发生改变