Pat乙级 1045 快速排序

• 思路
• 代码

题目网址
https://pintia.cn/problem-sets/994805260223102976/problems/994805278589960192

思路

25分的题直接暴力估计会超时。本题中主元的定义可以看成这样：左边没有比它大的，右边没有比它小的。用两个for循环分别从头和从尾扫一遍就可以了，用额外数组vis标记下。最后要额外输出一个换行，保证主元个数为0的情况的正确性，对应的测试点为测试点2–格式错误。

代码

#include<iostream> #define MAX 100005using namespace std;int data[MAX]; int vis[MAX] = {0};int main() {int n;int Max;int Min;int flag = 0;int cnt = 0; cin >> n;for (int i = 0; i < n; i ++)cin >> data[i];Max = -1;for (int i = 0; i < n; i ++) {if (data[i] >= Max) {Max = data[i];vis[i] = 1;}elsevis[i] = 0;}Min = data[n - 1];for (int i = n - 1; i >= 0; i --) {if (data[i] <= Min) {Min = data[i]; // vis[i] = 1;}elsevis[i] = 0;}for (int i = 0; i < n; i ++) {if (vis[i] == 1)cnt ++;} cout << cnt << endl;for (int i = 0; i < n; i ++) {if (vis[i] == 1){if (flag == 0)cout << data[i];elsecout << " " << data[i];flag ++;}}cout << endl;return 0; }

总结

以上是生活随笔为你收集整理的Pat乙级 1045 快速排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。