- 初步思路:sort排序数组,看每个元素的下标是否变化
- 但是可能有下标不变的元素,仍然不能作为主元pivot
- 因为有可能:7, 8, 9, 5, 1, 3, 2,这里排序后5的位置下标不变,但它不是主元
- 所以排序后还要借助原数组该位置元素之前的最大值来判断主元
- 即 大于原数组该位置前的的最大值 + 排序后位置不变
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int N = 0;
vector<int> nums;
vector<int> ret;
int main()
{
cin >> N;
nums.resize(N);
unordered_map<int, int> index;
for(int i = 0; i < N; ++i)
{
cin >> nums[i];
}
vector<int> tmp(nums);
sort(nums.begin(), nums.end());
int max = 0;
for(int i = 0; i < N; ++i)
{
if(nums[i] == tmp[i] && nums[i] > max)
ret.push_back(nums[i]);
if(tmp[i] > max) max = tmp[i];
}
cout << ret.size() << endl;
if(ret.size() == 0)
cout << endl;
if(ret.size())
cout << ret[0];
for(int i = 1; i < ret.size(); ++i)
cout << " " << ret[i];
return 0;
}