PAT-B 1045. 快速排序(25)

传送门

https://www.patest.cn/contests/pat-b-practise/1045

题目

著名的快速排序算法里有一个经典的划分过程:我们通常采用某种方法取一个元素作为主元,通过交换,把比主元小的元素放到它的左边,比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列,请问有多少个元素可能是划分前选取的主元?
例如给定N = 5, 排列是1、3、2、4、5。则:

  • 1的左边没有元素,右边的元素都比它大,所以它可能是主元;
  • 尽管3的左边元素都比它小,但是它右边的2它小,所以它不能是主元;
  • 尽管2的右边元素都比它大,但其左边的3比它大,所以它不能是主元;
  • 类似原因,4和5都可能是主元。

因此,有3个元素可能是主元。
输入格式:
输入在第1行中给出一个正整数N(<= 10^5); 第2行是空格分隔的N个不同的正整数,每个数不超过10^9。
输出格式:
在第1行中输出有可能是主元的元素个数;在第2行中按递增顺序输出这些元素,其间以1个空格分隔,行末不得有多余空格。
输入样例:
5
1 3 2 4 5
输出样例:
3
1 4 5

分析

这道题我看到时间限制是200ms,如果用题目中给的计算方法,也就是暴力法,应该是会超时的,因为比较次数有10^5^2次,所以想了一个稍微简单点的算法。最多循环2*10^5即可。
1.首先存入数组的时候,就比较一次大小,将当前下标前面的最大数存入另一个数组中,便于之后比较。
例如:输入 1 3 2 4 5
最大数的数组 0 1 3 3 4
说明:下标为0的位置放的是1之前的最大数,默认为0;下标为1的位置放的是3之前的最大数,是1;下标为2的位置放的是2之前的最大数,是3;下标为3的位置放的是4之前的最大数,还是3;下标为4的位置放的是5之前的最大数,是4。
2.在输入完成后,最大数数组也建立好了,然后就是要比较后面的最小数是否小于前面的数了,这里开始我的想法是也建立一个最小数的数组,发现没有那个必要,而且比较耗时,只需要用一个变量来记录最小数即可,在遍历的过程中和最大数数组比较,若大于对应下标的最大数数组,且小于后面的最小数,则将该数push进作为结果的数组,这里我本来是想push_front的,但是发现没有这个方法,于是就倒着放了,这也没有任何影响的,再输出结果的时候倒着输出就好了。
3.倒着输出结果的数组,注意输出第一项的时候不要数组越界即可。

源代码

//C/C++实现
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    vector<int> big(n); //存入当前下标前面的最大的数 
    int max = 0;
    for(int i = 0; i < n; ++i){
        scanf("%d", &v[i]);
        big[i] = max;
        if(v[i] > max){ //更新最大值 
            max = v[i];
        }
    }
    int small = 1000000001;
    vector<int> result; 
    for(int i = n - 1; i >= 0; --i){
        if(v[i] > big[i] && v[i] < small){
            result.push_back(v[i]);
        }
        if(v[i] < small){ //更新最小值 
            small = v[i];
        }
    }
    int size = result.size();
    printf("%d\n", size);
    if(size - 1 >= 0){ //不加判断的话,如果没有符合的情况,会下标越界 
        printf("%d", result[size - 1]);
    }
    for(int i = size - 2; i >= 0; --i){
        printf(" %d", result[i]);
    }
    printf("\n");
    return 0;
}

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器