美文网首页
Leetcode题集

Leetcode题集

作者: 柯原哀 | 来源:发表于2017-12-20 15:58 被阅读14次

    283.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.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,移到数组的最后面,其他元素按照数组的前后顺序排列。
    要求:不能新建数组,而且最小化操作的次数。

    我自己的错误解法

    解法是遇到0的时候把这个元素移到最后面,然后其他元素往前移动1位,但是有个问题是,遇到[0,0,1]这种连续几个0的数组时会报错,因为移动之后,0往前移动,但是因为数组+1,所以并没有判断移到0位的数字。

    public void moveZeroes (int nums []){
            int length = nums.length;
            int count = 0;
            for (int i = 0; i <= length - 1; i++) {
                if (nums[i] == 0 && (i + count < length)) {
                    count++;
                    for (int j = i; j <= length - 2 - i; j++) {
                        nums[j] = nums[j + 1];
                    }
                    nums[length - 1 - i] = 0;
                }
    }
    
    正确解法

    讨论区的解法,是遍历数组,然后初始化一个标记值为0,判断数组中不为0元素的索引值,当数组不为0的时候,标记值自增,自增的次数代表 数组不包含为0的元素的索引值,其他不为0的元素只需赋值在这个索引值之后即可。
    而在交换数组值的时候,只需要将为0数组的值赋给临时变量,当前不为0的数组值赋给索引值为标记值的数组元素,然后将临时变量赋给之前判断的不为0的数组值。
    例如: int [ ] nums = [ 1, 1, 0, 0, 0, 1 ] 判断,cur++ 之后等于2,也即此时数组 nums[0]、nums[1]不为0,其他不为0的元素,只需赋给num[2]即可。而判断语句就是实现这样的功能:

    temp = nums [2] , nums[2]=nums[5], nums[5]=temp

    public void moveZeroes (int nums []) { 
            if (nums == null || nums.length == 0) {
                return;
            }
            int cur = 0;
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i] != 0) {
                    int temp = nums[cur];
                    nums[cur++] = nums[i];
                    nums[i] = temp;
                }
            }
        }
    

    相关文章

      网友评论

          本文标题:Leetcode题集

          本文链接:https://www.haomeiwen.com/subject/ivigwxtx.html