资讯专栏INFORMATION COLUMN

[LintCode] Move Zeroes

Mr_houzi / 646人阅读

Problem

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.

Notice

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Example

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

Solution A too-clever method
class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0, j = 0;
        while (i < nums.length && j < nums.length) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
            i++;
        }
    }
}
A just-so-so method
public class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0, j = i+1;
        while (j < nums.length) {
            if (nums[i] != 0) {
                i++;
                j++;
            }
            else {
                if (nums[j] == 0) j++;
                else {
                    swap(nums, i, j);
                    i++;
                }
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
    

Update 2018-8

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length < 2) return;
        int i = 0, j = 1;
        while (j < nums.length) {
            if (nums[i] != 0) {
                i++;
                j++;
            } else {
                if (nums[j] == 0) {
                    j++;
                } else {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    i++;
                }
            }
        }
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/65999.html

相关文章

  • [LintCode/LeetCode/CC] Set Matrix Zeroes

    摘要:把矩阵所有零点的行和列都置零,要求不要额外的空间。对于首行和首列的零点,进行额外的标记即可。这道题我自己做了四遍,下面几个问题需要格外注意标记首行和首列时,从到遍历时,若有零点,则首列标记为从到遍历,若有零点,则首行标记为。 Problem Given a m x n matrix, if an element is 0, set its entire row and column t...

    zhangwang 评论0 收藏0
  • Leetcode PHP题解--D68 283. Move Zeroes

    摘要:题目链接题目分析给定一个整数数组,将值为的元素移动到数组末尾,而不改动其他元素出现的顺序。再在去后的元素末尾填充到计算出的数组长度。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 D68 283. Move Zeroes 题目链接 283. Move Zeroes 题目分析 给定一个整数数组,将值为0的元素移动到数组末尾,而不改动其他元素出现的顺序。 思路 计算总共有多少个元素。 再...

    xiongzenghui 评论0 收藏0
  • [Leetcode] Move Zeroes 移动零

    摘要:双指针压缩法复杂度时间空间思路实际上就是将所有的非数向前尽可能的压缩,最后把没压缩的那部分全置就行了。比如,先压缩成,剩余的为全置为。过程中需要一个指针记录压缩到的位置。 Move Zeroes Given an array nums, write a function to move all 0s to the end of it while maintaining the rel...

    baiy 评论0 收藏0
  • LeetCode 283:移动零 Move Zeroes

    摘要:给定一个数组,编写一个函数将所有移动到数组的末尾,同时保持非零元素的相对顺序。尽量减少操作次数。换个思路,把非数字前移,不去管数字。这样遍历完之后,数组索引从到之间的数值即为所求得保持非零元素的相对顺序,而之后的数值只需要全部赋值即可。 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 Given an array nums, write ...

    tianyu 评论0 收藏0
  • LeetCode 283:移动零 Move Zeroes

    摘要:给定一个数组,编写一个函数将所有移动到数组的末尾,同时保持非零元素的相对顺序。尽量减少操作次数。换个思路,把非数字前移,不去管数字。这样遍历完之后,数组索引从到之间的数值即为所求得保持非零元素的相对顺序,而之后的数值只需要全部赋值即可。 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 Given an array nums, write ...

    seanlook 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<