leetcode 283. Move Zeroes
Move Zeroes:题目链接
解法1：双指针之快慢指针
基本思想：将[0,slow）存放非零元素，[slow,数组长度)存放0，fast用来遍历整个数组，当发现满足条件的元素，放入[0,slow)区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.Arrays;
public class Solution1 {
// 时间复杂度 O(N) 空间复杂度O(1) 双指针
public static void moveZeroes(int[] nums) {
int slow = 0; // nums中, [0...slow)的元素均为非0元素
for (int fast = 0; fast < nums.length; ++fast) {
if (0 != nums[fast]) {
nums[slow++] = nums[fast];
}
}
// [slow , nums.length) 存放0
for (int i = slow; i < nums.length; ++i) {
nums[i] = 0;
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
System.out.println(Arrays.toString(nums));
}
}
|
解法2:优化解法1
在解法1的基础上，不需要将[slow , nums.length)单独拿出来赋值为0，在快慢指针进行的过程中，就已经完成了
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
| import java.util.Arrays;
public class Solution2 {
public static void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
// 时间复杂度 O(N) 空间复杂度O(1) 双指针
public static void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; ++fast) {
if (0 != nums[fast]) {
swap(nums, slow++, fast);
}
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
System.out.println(Arrays.toString(nums));
}
}
|
解法3
基本思想：遍历nums[]数组，不等于0的元素，暂存在临时数组res[]中，最后将最终结果再复制给nums[]
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
| import java.util.Arrays;
public class Solution3 {
// 时间复杂度 O(N) 空间复杂度O(N)
public static void moveZeroes(int[] nums) {
int[] res = new int[nums.length];
int k = 0;
// 非零元素存到res[]
for (int i = 0; i < nums.length; ++i) {
if (0 != nums[i]) {
res[k++] = nums[i];
}
}
for (int i = k; i < nums.length; ++i) {
res[i] = 0;
}
for (int i = 0; i < nums.length; ++i) {
nums[i] = res[i];
}
}
public static void main(String[] args) {
int[] nums = { 0, 1, 0, 3, 12 };
moveZeroes(nums);
System.out.println(Arrays.toString(nums));
}
}
|
ps：源代码链接
