CTF of Z2BNS
0%

移动零

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 888 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

示例1：

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

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

遍历数组，删除元素0然后在末尾添加一个元素0,注意删除元素后数组元素的索引。

c++代码：(执行用时24ms，击败10.55%，内存消耗9.1M，击败22.73%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;++i){
            if(nums[i]==0){
                nums.erase(nums.begin()+i);
                nums.emplace_back(0);
                //前面删除一个0
                --i;
                --n;
            }
        }
        
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：双指针

思路及解法

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：

左指针左边均为非零数；

右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

c++代码：(执行用时12ms，击败49.15%，内存消耗9.2M，击败10.44%）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为序列长度。每个位置至多被遍历两次。
  • 空间复杂度：$O(1)$。只需要常数的空间存放若干变量。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

自己的方法效率还是不行，vector容器删除和插入元素比较慢（需要前后元素前移或后移），优势是查找元素比较快（下表索引），所以自己使用的erase()函数和emplace_back()函数效率都不太高。而官方题解使用的是双指针还挺巧妙的，将左指针指向的零与右指针指向的非零数交换。双指针方法还挺常用的，以后多多使用吧。

------------- THE END! THANKS! -------------