1101 Quick Sort (25 分)

题目传送门：1101 Quick Sort (25 分)

一、题目大意

快速排序中，有个partition函数，是选定一个标兵，然后将比它小的数移动到它左侧，比它大的数移动到右侧。

现在给定一个数组，判断数组中的元素会不会是一个标兵（即判断它左边的数是不是都小于等于它，右侧的数是不是都大于等于它）。数组中第一个数只需要考虑它右边的数是不是都比它大即可。数组中最后一个数只需要考虑它左边的数是不是都比它小即可。

二、解题思路

打两个表，一个表leftMax存的是在每一位处，它左边所有数中的最大值。另一个表rightMin存的是在每一位处，它右边所有数中的最小值。（这两个表可以O(N)内迭代生成，见代码）

有了这两个表后，我们就可以枚举数组元素了，判断条件：
v[i] >= leftMax[i] and v[i] <= rightMin[i]
如果当前位大于等于他左侧最大的值，小于等于他右侧最小的值，则是符合partition的标兵

三、AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int>v(n);
	for(auto&i: v){
		cin >> i;
	}
	vector<int>leftMax(n);
	leftMax[0] = INT_MIN;
	for(int i = 1; i < n; i++){
		leftMax[i] = max(leftMax[i-1], v[i-1]);// 迭代统计出当前位左侧最大的值
	}
	vector<int>rightMin(n);
	rightMin[n-1] = INT_MAX;
	for(int i = n-2; i >= 0; i--){
		rightMin[i] = min(rightMin[i+1], v[i+1]);// 迭代统计出当前位右侧最小的值
	}
	vector<int>res;
	for(int i = 0; i < n; i++){
		if(v[i] >= leftMax[i] and v[i] <= rightMin[i]){// 如果当前位大于等于他左侧最大的值，小于等于他右侧最小的值，则是符合partition的标兵
			res.push_back(v[i]);
		}
	}
	sort(res.begin(), res.end());// 别忘了题目要求增序输出
	cout << res.size() << endl;
	for(int i = 0; i < res.size(); i++){
		if(i)cout << " " << res[i];
		else cout << res[i];
	}
	cout << endl;
}

  

 

  
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
  
29
  
30
  
31
  
32
  
33
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/100574296