LeetCode 283. 移动零【c++/java详细题解】

x33g5p2x  于10个月前 转载在 C/C++  
字(0.9k)|赞(0)|评价(0)|浏览(107)

1、题目

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数。

2、思路

**(双指针)**O ( n ) O(n)O(n)

给定一个数组 nums,要求我们将所有的 0 移动到数组的末尾,同时保持非零元素的相对顺序。

样例:

如样例所示,数组nums = [0,1,0,3,12],移动完成后变成nums = [1,3,12,0,0] ,下面来讲解双指针的做法。

我们定义两个指针,i指针和k指针,i指针用来遍历整个nums数组,k指针用来放置nums数组元素。然后将非0元素按照原有的相对顺序都放置到nums数组前面,剩下的位置都置为0。这样我们就完成了0元素的移动,同时也保持了非0元素的相对顺序。

具体过程如下:

  • 1、定义两个指针ik,初始化i = 0k = 0
  • 2、i指针向后移动,遍整个nums数组,如果 nums[i] != 0,也就是说遇到了非0元素,此时我们就将nums[i]元素放置到nums[k]位置,同时k++后一位。
  • 3、最后将k位置之后的元素都赋值为0

实现细节:

遍历数组可以使用for(int x : nums),这样就少定义一个指针,代码也显得更加简洁。

**时间复杂度分析:**O ( n ) O(n)O(n) ,n nn是数组的长度,每个位置只被遍历一次。

**时间复杂度分析:**O ( 1 ) O(1)O(1) ,只需要常数的空间存放指针变量。

3、c++代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k = 0;
        for(int x : nums)
            if(x != 0) nums[k++] = x;
        while(k < nums.size())  nums[k++] = 0;        
    }
};

4、java代码

class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        for(int x : nums)
            if(x != 0) nums[k++] = x;
        while(k < nums.length)  nums[k++] = 0;      
    }
}

原题链接:283. 移动零

相关文章