LeetCode283-Move Zeroes

题目

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

分析

解法一:暴力开辟新空间

第一眼看上去马上想到开辟一个与nums等长的空数组,然后设立两个高低指针low和high分别作为新数组游标,再开始逐一考察nums元素,若非0则将其置于低位,若为0则置于高位。这种方法虽然是\(O(n)\)的,但因为最后还要去更新nums数组才能实现改变,所以还是有少量的时间损耗。总之就是这种解法并不那么优雅。

解法二:非0数置于低位

仔细想其实我们根本不需要开辟新数组,直接对原数组采用类似的操作即可。根据题意,首先想到的是“遍历数组nums,如果碰到0则把它置于高位”,但转念一想,那高位原来的数1.要么会被覆盖 2.要么就交换到刚才0所在位置,可这样所有非0数的原始相对顺序就打乱了,因此行不通。

所以就换了种思路,想能不能变成“如果碰到非0则把它置于低位”,还真成了。因为遍历数组的游标及等待被覆盖的low指针均是从低位开始往高位移动的,所以这就保证了相对顺序一定不会有闪失,所以,只要把所有非0的数照顾到了,其它位置自然就全部为0了。但落实到具体实现上有个小技巧可以节约少许时间,就是我们每次将非0数覆盖到low处后,原来的位置i处的元素就可以置为0了(但要保证low != i,否则白覆盖了)。

代码

解法一

public class Solution {
    public void moveZeroes(int[] nums) {
        int[] res = new int[nums.length];
        int low = 0;
        int high = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                res[high] = 0;
                high--;
            } else {
                res[low] = nums[i];
                low++;
            }
        }
        
        for (int i = 0; i < nums.length; i++)
            nums[i] = res[i];
    }
}

解法二

public class Solution {
    public void moveZeroes(int[] nums) {
        
        int low = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[low] = nums[i]; //覆盖低处
                if(low != i) //是否需要把当前位置置为0
                    nums[i] = 0;
                    
                low++;
            }
        }
    }
}

Leave a Comment.