首页 > 代码库 > LeetCode - 268. Missing Number - stable_sort应用实例 - ( C++ ) - 解题报告

LeetCode - 268. Missing Number - stable_sort应用实例 - ( C++ ) - 解题报告

1.题目大意

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:

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

解析:给定一个组的数字,把所有0都移到数组的末端,其它数字顺序不改变。比如给定的是nums = [0, 1, 0, 3, 12],那么输出结果应该是 [1, 3, 12, 0, 0]。要求尽量不要用复制数组的方式来实现,尽量减小操作次数。

 

2.思路解析

像我这种弱渣看到,第一个想法就是非常基础的做法——把没用的删掉,再在后面的加上0来就好了。

比如这种弱渣做法:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;)
        {
            if(nums[i]==0)  {n--;nums.erase(nums.begin()+i);nums.push_back(0);continue;}
            i++;
        }
    }
};

不过runtime看起来比较难看,“Your runtime beats 41.41% of cpp submissions.”。然后我就去讨论区看了看,发现一个特别强的思路:原代码链接

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        stable_sort(nums.begin(), nums.end(), [](const int& x, const int& y){return (x && !y);});
    }
};

这个思路

93.96% beat rate

stable_sort的第一个参数是起始位置,第二个参数是终止位置,第三个参数则是一个判断。

比如说后面return的如果是x>y,那么这个数组会变成从大到小排序的数组;在这题中,则代表着x是非0数并且y是0的时候就调换顺序,最终0会调整到队尾。

LeetCode - 268. Missing Number - stable_sort应用实例 - ( C++ ) - 解题报告