（PAT 1101)Quick Sort (递推法)

╰半夏微凉° 2022-03-26 03:48 199阅读 0赞

There is a classical process named **partition** in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?

For example, given N=5 and the numbers 1, 3, 2, 4, and 5. We have:

*  1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;
 *  3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;
 *  2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;
 *  and for the similar reason, 4 and 5 could also be the pivot.

Hence in total there are 3 pivot candidates.

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives a positive integer N (≤105). Then the next line contains N distinct positive integers no larger than 109. The numbers in a line are separated by spaces.

### Output Specification: ###

For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

### Sample Input: ###

5
    1 3 2 4 5

### Sample Output: ###

3
    1 4 5

解题思路:

这题没必要去写一个快排然后找pivot逐个比较,题目的意思是,判断每个元素左边的元素是否都小于当前元素且右边的元素是否都大于当前元素,如果都满足的话,输出该元素即可

这个用递推法就可以解决了,先从左向右递推,给出数组中当前位置为止的最大元素

然后从右向左推,给出数组中当前位置为止最小的元素

然后把原数组中的元素依次和递推数组中的元素比较,就可以了

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int MAXN = 100010;
    long int numbers[MAXN];
    long int forwards[MAXN];
    long int backs[MAXN];
    int  N;
    int main() {
    	scanf("%d", &N);
    	for (int i = 0; i < N; ++i) {
    		scanf("%d", &numbers[i]);
    	}
    	//正推
    	int biggest = numbers[0];
    	forwards[0] = numbers[0];
    	for (int j = 1; j < N; ++j) {
    		forwards[j] = forwards[j - 1];  //递推
    		if (numbers[j] > biggest) {
    			biggest = numbers[j];
    			forwards[j] = biggest;
    		}
    	}
    	//逆推
    	int smallest = numbers[N - 1];
    	backs[N-1] = numbers[N - 1];
    	for (int k = N - 2; k >= 0; --k) {
    		backs[k] = backs[k+1];
    		if (numbers[k] < smallest) {
    			smallest = numbers[k];
    			backs[k] = smallest;
    		}
    	}
    	vector<long int> res;
    	for (int i = 0; i < N; ++i) {
    		if (numbers[i] >= forwards[i] && numbers[i] <= backs[i]) {
    			res.push_back(numbers[i]);
    		}
    	}
    	
      cout << res.size() << endl;
    	for (int i = 0; i < res.size(); ++i) {
    			cout << res[i];
    			if(i < res.size()-1){
    			  cout<<" ";
    			}
    	}
    	cout<<endl;  //必须要有换行
    	return 0;
    }