PAT A1101 Quick Sort(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1101 Quick Sort
中文版:B1045 快速排序

解题思路

找到每个数字中左边的最大元素、右边的最小元素,再与该位置的元素进行比较,即可获知该元素是否可能为主元。如果使用多次循环寻找最值将可能超时。因此,这里用两个数组分别存储每个位置左右的最值,只需要两次遍历,即可获得所需数据,最后再进行一次遍历即可获得最终结果。

可以将结果存放到可变数组中,最后排个序。但因为数字没有重复,因此也可以直接将结果存到集合中,集合将自动排序获得升序序列。

易错点

  • 结尾一定要输出换行,否则当结果个数为 0 时,第二行没有输出将报错。

也许陌生的知识点

  • y = max(a, b)
    • 获取两个元素中的较大值
    • 需要头文件 algorithm
  • set <int> ans;
    • 创建了一个集合,用于存放结果
    • ans.insert(S[i])
      • 向集合中插入一个元素
    • 需要头文件 set
  • for(auto it = ans.begin(); it != ans.end(); it++){ }
    • 可用于遍历 map/vector/set 等容器, auto 实现自动匹配对应迭代器类型
    • it 为迭代器, *it 为对应元素

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
int main(){
int N, S[100010], Left_max[100010], Right_min[100010];
set <int> ans;
scanf("%d", &N);
for(int i = 0; i < N; i++){ // 获得左边最大数的序列
scanf("%d", &S[i]);
if(i == 0) Left_max[0] = S[0];
else Left_max[i] = max(Left_max[i - 1], S[i - 1]);
}
for(int i = N - 1; i >= 0; i--){ //获得右边最小数的序列
if(i == N - 1) Right_min[i] = S[i];
else Right_min[i] = min(Right_min[i + 1], S[i + 1]);
}
for(int i = 0; i < N; i++){ // 判断是否可能为主元
if(S[i] >= Left_max[i] && S[i] <= Right_min[i]) ans.insert(S[i]);
}
printf("%d\n", ans.size());
for(auto it = ans.begin(); it != ans.end(); it++){
if(it != ans.begin()) printf(" ");
printf("%d", *it);
}
printf("\n"); // 不能少,否则会有格式错误
return 0;
}