1045. 快速排序(25)
著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定N = 5, 排列是1、3、2、4、5。则：
1的左边没有元素，右边的元素都比它大，所以它可能是主元； 尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元； 尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元； 类似原因，4和5都可能是主元。
因此，有3个元素可能是主元。
输入格式：
输入在第1行中给出一个正整数N（<= 105）； 第2行是空格分隔的N个不同的正整数，每个数不超过109。
输出格式：
在第1行中输出有可能是主元的元素个数；在第2行中按递增顺序输出这些元素，其间以1个空格分隔，行末不得有多余空格。
输入样例： 5 1 3 2 4 5 输出样例： 3 1 4 5 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 CAO, Peng 分析：通过正序与逆序两趟遍历，分别找出比左边数都大和比右边数都小的数并做标记，两者的交集即为最后所求。 #include <iostream> #include <vector> using namespace std; int main() { int N; cin >> N; vector<int> n(N); // 索引代表可能为主元位置的坐标，值全部初始化为0 vector<int> posb_index(N, 0); vector<int> final; for (int i = 0; i < N; i++) { cin >> n[i]; } int max = n[0] - 1, min = n[N - 1] + 1; for (int i = 0; i < N; i++) { /*正向遍历，找到比左边都大的数，在相应位置+2； n[0] 默认为符合该条件*/ if (n[i] > max) { posb_index[i] += 2; max = n[i]; } /*逆向遍历，找到比右边都小的数，在相应位置-1； n[N-1] 默认为符合该条件*/ if (n[N - 1 - i] < min) { posb_index[N - 1 - i] -= 1; min = n[N - 1 - i]; } } /*经过遍历之后，符合条件的位置应该为2-1 = 1； 由于需要先输出主元个数，所以要储存主元的值*/ for (int i = 0; i < N; i++) { if (posb_index[i] == 1) final.push_back(n[i]); } /*输出前无需排序，因为快速排序每一趟都会把主元位置 放到最终位置上，所以服从升序*/ cout << final.size() << endl; for (int i = 0; i < final.size(); i++) { cout << final[i]; if (i != final.size() - 1) cout << " "; } cout << endl; // 需要加一个换行，不然有一个测试点不能通过 return 0; }