题目链接: 1045 快速排序 (25 分)
这道题目困扰我好久了. 我知道自己数据结构与算法的基础知识没有掌握好. 这是其中内部排序的
快速排序.
我刚开始的思路是遍历整个数组, 针对每一个元素判断其是否满足主元的条件, 即
当前元素大于之前元素的最大值 && 当前元素小于之后元素的最小值. 确定之前元素的最大值比较容易,
遍历时每次刷新最大值即可, 但是之后元素的最小值缺难到了我!
参考网上大佬的想法: 可以这样做, 事先进行两次遍历, 第一次遍历从前向后, 用一个数组记录每个位置
之前的最大元素; 第二次遍历从后向前, 用一个数组记录每个位置之后的最小元素.
最后一次遍历, 判断该元素是否满足条件并记录.
自己有这个想法, 但是我逻辑太混乱了, 没能实现, 参考网上的如下:
代码一:
- #include <bits/stdc++.h>
- using namespace std;
- const int N=100001;
- int a[N];
- int LeftMax[N],RightMin[N];
- int ans[N];
- int main()
- {
- int n;
- scanf("%d",&n);
- for(int i=0;i<n;i++)
- scanf("%d",a+i);
- LeftMax[0]=a[0];RightMin[n-1]=a[n-1];
- //LeftMax[i] 记录下标 i 之前的最大元素的值. LeftMax[0] 默认为 a[0], 不冲突
- for(int i=1;i<n;i++)
- LeftMax[i]=max(LeftMax[i-1],a[i-1]);
- for(int i=n-2;i>=0;i--)
- RightMin[i]=min(RightMin[i+1],a[i+1]);
- int count=0;
- for(int i=0;i<n;i++)
- {
- if(a[i]>=LeftMax[i]&&a[i]<=RightMin[i])
- ans[count++]=a[i];
- }
- printf("%d\n",count);
- for(int i=0;i<count;i++)
- {
- printf("%d",ans[i]);
- if(i!=count-1)
- printf(" ");
- }
- printf("\n");
- return 0;
- }
- View Code
之后又参考网上的其它解法,
- #include <bits/stdc++.h>
- using namespace std;
- int a[100001];
- int b[100001];
- vector<int>ans;
- int main()
- {
- int n;
- cin>>n;
- for(int i=0;i<n;i++)
- {
- scanf("%d",&a[i]);
- b[i]=a[i];
- }
- sort(b,b+n);
- int curmax=0;
- for(int i=0;i<n;i++)
- {
- if(a[i]==b[i]&&a[i]>curmax)
- ans.push_back(a[i]);
- if(a[i]>curmax)
- curmax=a[i];
- }
- sort(ans.begin(),ans.begin()+ans.size());
- cout<<ans.size()<<endl;
- for(int i=0;i<ans.size();i++)
- {
- cout<<ans[i];
- if(i!=ans.size()-1)
- cout<<" ";
- }
- cout<<endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2930755.html