LeetCode之283. Move Zeroes

时间:2023-03-08 15:38:44

LeetCode之283. Move Zeroes

----------------------------------------------------------------------

解法一:空间换时间

我使用的办法也是类似于“扫描-拷贝”这种的,不过稍微有些不同,是使用了一个队列来记录空闲的位置信息,然后每次需要移动的时候出队列就可以了,这样可以做到最少的拷贝次数。

扫描到一个元素的时候情况可能有以下几种:
nums[i]==0   --> 放入下标队列,没有元素移动
nums[i]!=0 && !queue.isEmpty()  --> 从位置队列头取出一个位置j,将这个值nums[i]赋给取出的位置nums[j],同时将此位置i(值已移动,可用)放入位置队列
nums[i]!=0 && queue.isEmpty()  --> 说明之前的都已经好了,不需要进行任何操作

时间复杂度是线性级别的,以空间换取时间。

AC代码如下:

public class Solution {
public void moveZeroes(int[] nums) {
List<Integer> queue=new ArrayList<>();
for(int i=0;i<nums.length;i++){
if(nums[i]!=0 && !queue.isEmpty()){
nums[queue.remove(0)]=nums[i];
queue.add(i);
}else if(nums[i]==0){
queue.add(i);
}
}
Arrays.fill(nums,nums.length-queue.size(),nums.length,0);
}
}

解法二:维护两个指针 O(n^2)

维护两个指针,不断的往前移动。

AC代码:

public class Solution {
public void moveZeroes(int[] nums) {
int i=0,j=0;
while(i<nums.length){
if(nums[i]==0){
j=Math.max(i,j);
while(j<nums.length && nums[j]==0) j++;
if(j==nums.length) return ;
nums[i]=nums[j];
nums[j++]=0;
}
i++;
}
}
}

题目来源: https://leetcode.com/problems/move-zeroes/