题目描述
acwing 1591 快速排序
样例
5
1 3 2 4 5
算法1
$O(n)$
先复制原数组，然后把原数组排序，如果两个数组对应位置相等的话再判断当前点与左半边最大值的关系
时间复杂度 O(n)
参考文献 pat 甲级
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=100010;
int a[N],b[N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a,a+n);
int lmax=0;
vector<int> res;
for(int i=0;i<n;i++)
{
if(a[i]==b[i]&&a[i]>lmax) res.push_back(a[i]);
if(b[i]>lmax) lmax=b[i];
}
cout<<res.size()<<endl;
if(res.size()==0) puts("");
else
{
for(int i=0;i<res.size();i++) cout<<res[i]<<" ";
}
return 0;
}
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N=100010;
int a[N],b[N];
int n;
int main()
{
cin>>n;
for(int i=0;i[HTML_REMOVED]>a[i];
b[i]=a[i];
}
sort(a,a+n);
int lmax=0;
vector[HTML_REMOVED] res;
for(int i=0;i[HTML_REMOVED]lmax) res.push_back(a[i]);
/如果他排完序后比排序前的位置靠后说明原先他左边有比他小的数
反之如果他排完序后比排序后的位置靠前说明原来他的左边有比他大的数/
if(b[i]>lmax) lmax=b[i];
//这里的b[i]没有排序，所以lmax一直是左半边最大的数
}
}
//时间复杂度是O(n);
//这里我写了一点点注释，帮助理解一下
可以啊
##妙啊，tql