算法题丨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.

描述

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.
Note:
1.You must do this in-place without making a copy of the array.
2.Minimize the total number of operations.

示例

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

算法分析

难度:低
分析:给定一个数组,将所有为0的元素都移动到数组的末尾,并保持非0的元素排序保持不变。
思路:首先,思考满足第1个条件很简单,就是遍历数组,判断当前元素是否为0,如果是0,将0跟当前元素互换一下,遍历完数组就可以了。但是这样处理的话,并不能保证非0元素排序不变,所以,我们放弃这种思路。
那怎么保持非0元素的排序呢?我们考虑记录当前非0的个数索引index,遍历的时候,如果是非0元素,将数组[index]记录该元素,非0的个数索引index加1,下一个非0的就会记录在数组[index+1]中,依次类推,这样其实实现了非0元素顺序保存。最终数组[0,index)即为保持排序的非0元素。剩下的就很简单了,将数组[index]之后的元素全部置0就可以了。

代码示例(C#)

public void MoveZeroes(int[] nums)
{
    int index = 0;
    for (int i = 0; i < nums.Length; ++i)
    {
        if (nums[i] != 0)
        {
            //非0元素,记录排序
            nums[index++] = nums[i];
        }
    }
    //非0元素之后的元素全置0
    for (int i = index; i < nums.Length; ++i)
    {
        nums[i] = 0;
    }
}          

复杂度

  • 时间复杂度O (n).
  • 空间复杂度O (1).

附录

img_8f0a90f3cbaa0e044fb8bf7b13c4317b.jpe

文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

目录
相关文章
|
算法 C++
【C++11算法】move和move_backward
【C++11算法】move和move_backward
128 0
LeetCode 283. Move Zeroes
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
110 0
LeetCode 283. Move Zeroes
|
存储 索引
LeetCode 73. Set Matrix Zeroes
给定一个m * n 的矩阵,如果当前元是0,则把此元素所在的行,列全部置为0. 额外要求:是否可以做到空间复杂度O(1)?
103 0
LeetCode 73. Set Matrix Zeroes
|
算法 Python
LeetCode 283. 移动零 Move Zeroes
LeetCode 283. 移动零 Move Zeroes
LeetCode之Move Zeroes
LeetCode之Move Zeroes
99 0
|
索引 Python Java
LeetCode 283:移动零 Move Zeroes
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 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. 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作,不能拷贝额外的数组。
766 0
[LeetCode]--73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution us
983 0