Move Zeroes

页面导航:首页 > 软件编程 > java > Move Zeroes

Move Zeroes

来源:互联网 作者:脚本宝典 时间:2015-09-22 13:25 【

Givenanarraynums,writeafunctiontomoveall0‘stotheendofitwhilemaintainingtherelativeorderofthenon-zeroelements.Forexample,givennums=[0,1,0,3,12],aftercallingyourfunction,numsshouldbe[1,3,12,0,0].Note:Youmustdothisin-placewithoutmakingacopyo
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.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
一开始的想法是,遍历数组,遇到0就往后移,一直移动最后一步。代码如下
public class Solution {
    public static void moveZeroes(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0 && i != (nums.length - 1)) {
                for (int j = i; j < nums.length - 1; j++) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}
但是,发现001这个测试用例不对。
恩,发现问题了,因为第一个数为0,第二个0就没办法移动到最后了。
换一种思路,不遍历找0,而是遍历找非0,遇到非0,且不在第一位,就往前移,直到它前面不是0为止。
public class Solution {
    public static void moveZeroes(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && i != 0) {
                for (int j = i; j > 0 && nums[j - 1] == 0; j--) {
                    int temp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }
}
这样就解决了
其他方法
public static void moveZeroes(int[] nums) {
        int i = 0, j = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (j != i) {
                    nums[j] = nums[i];
                    nums[j] = 0;
                }
                j++;
            }
        }
    }
这种方法i遍历数组,只有当i指向为非0时,且ji不同时,j后移,将j处的数改成i处的数,并使i处的数字为0,ij同步后移,而当i指向为0时,只有i后移,j仍然指向0处。
还有一种更简单的方法
public void moveZeroes(int[] nums) {
    if (nums == null || nums.length == 0) return;        

    int insertPos = 0;
    for (int num: nums) {
        if (num != 0) nums[insertPos++] = num;
    }        

    while (insertPos < nums.length) {
        nums[insertPos++] = 0;
    }
}


Tags:

相关文章

    文章评论

    最 近 更 新
    热 点 排 行
    Js与CSS工具
    代码转换工具
    
    <