LeetCode - 268. Missing Number - stable_sort应用实例 - ( C++ ) - 解题报告
2024-09-04 11:44:36
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:
- You must do this in-place without making a copy of the array.
- 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会调整到队尾。
最新文章
- Asp.Net WebApi核心对象解析(上篇)
- PHP
- 细心很重要---猜猜这个SQL执行的什么意思
- iOS手势(滑动)返回的实现(自定义返回按钮)
- Linux之top命令
- C#抽象工厂模式的几种实现方法及比较
- 网络安全设备Bypass功能介绍及分析
- 【Node】fs
- Cohort Analysis Using Python
- Love myself...
- SharePoint 读取选项字段所有Choise
- @ResponseBody注解
- 覃超:Facebook的项目开发流程和工程师的绩效管理机制
- SSM 开发 Tars
- 2018-2019-2 网络对抗技术 20165227 Exp4 恶意代码分析
- seajs 使用文档
- 解决安装laravel/homestead vagrant环境报";A VirtualBox machine with the name &#39;homestead&#39; already exists.";的错误
- LightOj 1030 - Discovering Gold(dp+数学期望)
- centos killall安装
- C++雾中风景7:闭包