移动零

发表于 分类于 ， ， 阅读次数：

题目描述

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

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
class Solution {
    public void moveZeroes(int[] nums) {
        List<Integer> list=new LinkedList<>();
        for(int i=0;i<nums.length;i++)
        {
            list.add(nums[i]);
        }
        int length=nums.length;
        for(int i=0;i<length;i++)
        {
            if(list.get(i)==0)
            {
                list.remove(i);
                list.add(0);
                i--;
                length--;
            }
        }
        for(int i=0;i<list.size();i++)
        {
            nums[i]=list.get(i);
        }

    }
}

思路为将数组变为双向链表，遍历以后出现零就删除并在末尾添加零，再将双向链表变为数组。不过这种做法虽然简单，但是时间和空间复杂度都不行。

运行结果

执行用时：828 ms, 在所有 Java 提交中击败了5.05%的用户

内存消耗：44.3 MB, 在所有 Java 提交中击败了5.10%的用户

通过测试用例：74 / 74

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public void moveZeroes(int[] nums) {
		if(nums==null) {
			return;
		}
		//第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
		int j = 0;
		for(int i=0;i<nums.length;++i) {
			if(nums[i]!=0) {
				nums[j++] = nums[i];
			}
		}
		//非0元素统计完了，剩下的都是0了
		//所以第二次遍历把末尾的元素都赋为0即可
		for(int i=j;i<nums.length;++i) {
			nums[i] = 0;
		}
	}
}

作者：wang_ni_ma
链接：https://leetcode.cn/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/
来源：力扣（LeetCode）

此题思路为把不是零的数先往前推，用j来控制,当不是零的数放完后j到length的差就是赋值为零的数了，对比我的不用在链表上搜索目标值并删除，也不用链表数组反复转换，大大节省了运行时间。此题还应该多多留意为空的情况。