PAT乙级1045 || 快速排序（详解，C/C++示例，测试点分析）

Posted on In

快速排序

题目描述

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 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 个空格分隔，行首尾不得有多余空格。

输入样例

1
2
5
1 3 2 4 5

输出样例

1
2
3
1 4 5

问题解决

解题思想

题意很简单，暴力解法的思想也很简单，但是暴力解法都涉及两层循环，时间复杂度达O($n^2$)，测试时某些测试点会超时，如下面的代码1；

第二种方法是借鉴某大佬博客的方法，只需一边遍历，便可解决问题，时间复杂度为O(n)，具体做法是：输入的同时更新已输入数据的最大值，将本次输入数据与最大值进行比较，若小于最大值则本次输入的数据一定不可能是主元，淘汰此元素并用此元素淘汰前面未被淘汰的值比它大的元素，直到遇到第一个值比它小的元素为止，因为前面的元素都是递增的，因此，第一个值比它小的元素前面的元素都比它小。

第三种方法是利用主元的位置不变性，需要多次时间复杂度为O(n)的遍历。对输入的元素先排好序，然后与原序列相应位置元素对比，若相等则判断其是否比前面的最大值大（或者比后面的元素的最小值小），满足则其可能为主元，若不相等或者不满足比前面的最大值大（或者不满足比后面的元素的最小值小）都不可能是主元。由于是与已经排好序的序列的相应元素进行对比，故只需检查是否比前面的最大值大或者是否比后面的元素的最小值小中的一项即可。

坑点提醒

测试点2格式错误。需要在输出的最后输出换行，否则此测试点会出现格式错误。

代码示例（C/C++）

代码1——普通方法（部分运行超时）

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
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
using namespace std;
const int maxn = 100001;
int main()
{
    int n;
    scanf("%d",&n);
    int a[maxn],s[maxn];
    for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
        int flag1 = 0,flag2 = 0;
        for(int j = i - 1; j > 0; j--){
            if(a[j] > a[i]){
                flag1 = 1;
                break;
            }
        }
        if(!flag1){
            for(int k = i + 1; k < n; k++){
                if(a[k] < a[i]){
                    flag2 = 1;
                    break;
                }
            }
        }
        if(flag1||flag2){
            continue;
        }
        else{
            s[sum++] = a[i];
        }
    }
    printf("%d\n",sum);
    for(int i = 0; i < sum; i++){
        printf("%d",s[i]);
        if(i != sum - 1){
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

代码2——输入淘汰法（全部通过）

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
34
35
36
37
#include <cstdio>
using namespace std;
const int maxn = 100001;
int main()
{
    int n;
    scanf("%d",&n);
    int a[maxn] = {0},maxi = 0,maxa = 0;	//maxi最大下标
    for(int i = 0; i < n; i++){
        int temp;
        scanf("%d",&temp);
        if(temp > maxa){    //当前输入的值大于前面数的最大值
            maxa = temp;    //更新最大值
            a[maxi++] = maxa;   //该元素之前的部分元素可能是主元
        }
        else{   //该元素小于之前的最大值则其必不是主元
            for(int j = maxi - 1; j >= 0; j--){
                if(a[j] > temp){    //用该数淘汰前面的必不为主元的值
                    a[j] = 0;
                    maxi--;
                }
                else{   //只要有一个小于该值则后面的均小于该值
                    break;
                }
            }
        }
    }
    printf("%d\n",maxi);
    for(int i = 0; i < maxi; i++){
        printf("%d",a[i]);
        if(i != maxi - 1){
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

代码3——主元位置不变法（全部通过）

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
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100001;
int main()
{
    int n;
    scanf("%d",&n);
    int a[maxn],b[maxn];
    for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    sort(b,b + n);
    int sum = 0,maxa = 0;    //sum可能为主元的元素个数,maxa当前元素之前的最大值
    for(int i = 0; i < n; i++){
        if(a[i] > maxa&&a[i] == b[i]){    //当前元素大于之前元素的最大值且处于已排好序的位置
            sum++;
            maxa = a[i];    //更新最大值
        }
        else if(a[i] < maxa){
            b[i] = 0;
        }
        else{   //a[i] != b[i]但maxa > a[i]
            maxa = a[i];
            b[i] = 0;
        }
    }
    printf("%d\n",sum);
    int flag = 0;
    for(int i = 0; i < n; i++){
        if(b[i]){
            if(flag){
                printf(" %d",b[i]);
            }
            else{
                printf("%d",b[i]);
                flag = 1;
            }
        }
    }
    printf("\n");
    return 0;
}

题目来源：PAT乙级1045
作者：CHEN, Yue
单位：浙江大学

稀罕作者