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 快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。