移动零(Move Zeroes)
移动零(Move Zeroes)是一个常见的数组操作问题,题目要求将给定的整数数组中的所有0移动到数组的末尾,同时保持非零元素的相对顺序不变。下面是用Java实现的解决方案:
public class MoveZeroes {
public void moveZeroes(int[] nums) {
// 使用双指针方法
int left = 0; // 左指针指向当前已经处理好的序列的尾部
int right = 0; // 右指针指向待处理序列的头部
// 将非0元素依次移到数组的前面
while (right < nums.length) {
// 如果右指针指向的元素非0,则与左指针指向的元素交换,并将左指针右移
if (nums[right] != 0) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
}
// 右指针右移
right++;
}
}
}
解释每一步:
-
我们使用双指针方法来解决这个问题。左指针
left
指向当前已经处理好的序列的尾部,右指针right
指向待处理序列的头部。 -
我们使用
right
指针遍历数组,将非0元素依次移到数组的前面。 -
如果右指针指向的元素非0,则将其与左指针指向的元素交换,并将左指针右移。
-
右指针右移,继续遍历数组,直到右指针到达数组末尾。
这种解法的时间复杂度为 O(n),其中 n 是数组的长度。因为我们只需要遍历一次数组。空间复杂度为 O(1),因为只使用了常数级别的额外空间。