PAT A1101 Quick Sort(C++)

题目描述

解题思路

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

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

易错点

结尾一定要输出换行，否则当结果个数为 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 为对应元素

代码示例：

#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;
}