#P4003. 移动零
-
ID: 2205
Tried: 2163
Accepted: 685
Difficulty: 2
移动零
移动零
题目分析
本题的目标是将数组中的所有 0
移动到数组末尾,并保持其他非零元素的相对顺序,同时要求 原地修改 数组,即不能复制额外的数组。这意味着我们需要用 双指针 和 原地交换 技巧来高效地解决问题。
解题思路
我们可以使用 双指针法 来解决这个问题,其中一个指针 j
用来遍历整个数组,另一个指针 i
记录下一个应该放置非零元素的位置。具体做法如下:
- 初始化
i = 0
,用于记录非零元素应该存放的位置。 - 遍历数组:
- 遇到非零元素时,将其 移动到索引
i
位置,然后i
向前移动。 - 遇到
0
时,不做任何操作,继续遍历。
- 遇到非零元素时,将其 移动到索引
- 遍历结束后,所有
0
会自动被放置到数组末尾。
复杂度分析
- 时间复杂度:O(n),每个元素最多遍历一次,因此时间复杂度为线性。
- 空间复杂度:O(1),仅使用了常数额外空间,符合题目要求的 原地修改。
代码实现
Python 解法
class Solution:
def moveZeroes(self, nums):
n = len(nums)
i = 0 # 记录非零元素应放置的位置
# 遍历数组,将非零元素移到前面
for j in range(n):
if nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i] # 交换非零元素到前面
i += 1 # 移动非零元素位置索引
# 读入数据并调用函数
n = int(input().strip())
nums = list(map(int, input().split()))
Solution().moveZeroes(nums)
print(" ".join(map(str, nums)))
Java 解法
import java.util.*;
public class Main {
public class Solution {
public void moveZeroes(int[] nums) {
int i = 0; // 记录非零元素应存放的位置
// 遍历数组,将非零元素放到前面
for (int j = 0; j < nums.length; j++) {
if (nums[j] != 0) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++; // 更新非零存放位置
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 读取数组长度
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
Main main = new Main();
Solution solution = main.new Solution();
solution.moveZeroes(nums);
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + (i < n - 1 ? " " : ""));
}
}
}
C++ 解法
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0; // 记录非零元素应存放的位置
// 遍历数组,将非零元素放到前面
for (int j = 0; j < nums.size(); j++) {
if (nums[j] != 0) {
swap(nums[i], nums[j]); // 交换非零元素到前面
i++; // 更新非零存放位置
}
}
}
};
int main() {
int n;
cin >> n; // 读取数组长度
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
Solution solution;
solution.moveZeroes(nums);
for (int i = 0; i < n; i++) {
cout << nums[i] << (i < n - 1 ? " " : "");
}
return 0;
}
题目内容
给定一个数组nums,将所有 0移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
输入描述
输入共两行。
-
第一行为两个个整数n,代表数组nums的长度。
-
第二行为n个整数nums0,nums1,...,numsn−1,数字之间以空格分隔。
输出描述
输出操作后的数组,以空格分隔。
样例1
输入
5
0 1 0 3 12
输出
1 3 12 0 0
样例2
输入
1
0
输出
0
提示
- 1<=nums.length<=104
- −231<=nums[i]<=231−1
进阶
你能尽量减少完成的操作次数吗?