欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT 1045 快速排序

程序员文章站 2022-07-15 14:02:23
...

1045 快速排序(25 分)

著名的快速排序算法里有一个经典的划分过程:我们通常采用某种方法取一个元素作为主元,通过交换,把比主元小的元素放到它的左边,比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列,请问有多少个元素可能是划分前选取的主元?
例如给定 N=5, 排列是1、3、2、4、5。则:
1 的左边没有元素,右边的元素都比它大,所以它可能是主元;
尽管 3 的左边元素都比它小,但其右边的 2 比它小,所以它不能是主元;
尽管 2 的右边元素都比它大,但其左边的 3 比它大,所以它不能是主元;
类似原因,4 和 5 都可能是主元。
因此,有 3 个元素可能是主元。
输入格式:
输入在第 1 行中给出一个正整数 N(105); 第 2 行是空格分隔的 N 个不同的正整数,每个数不超过 109
输出格式:
在第 1 行中输出有可能是主元的元素个数;在第 2 行中按递增顺序输出这些元素,其间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:

5
1 3 2 4 5

输出样例:

3
1 4 5




解析

这题一看就知道暴力不能解决问题。所以要用空间换时间。
我是这样做的:

struct yes{
    int num;
    bool f1,f2;
};

定义一个struct结构体:f1表示该数是左边最大。f2表示该数是右边最大。
然后首先正着遍历一遍序列。并存储当前的最大值。如果当时在遍历的数小于这个最大值,就证明它不是主元。令f1=false。否则把该值设为最大值。
同理:逆序遍历一遍序列。并存储当前最小值。如果当时在遍历的数大于这个最小值。就证明它不是主元,令f2=false。否则把该值设为最小值。
最后:遍历一遍序列:如果f1,f2都是true,代表是主元


这题:测试点2我格式错误。看了别人的blog。原来是当没有可能的主元时,要输出(坑爹)

0
'\n'


Code:

#include<bits/stdc++.h>
using namespace std;
struct yes{
    int num;
    bool f1,f2;
};
int main()
{
    int N;
    cin>>N;
    vector<yes> data(N);
    for(int i=0;i<N;i++){
        cin>>data[i].num;
        data[i].f1=data[i].f2=true;
    }
    int min=data[N-1].num,max=data[0].num;
    for(int i=1;i<N;i++){
        if(data[i].num<max)
            data[i].f1=false;
        else
            max=data[i].num;
    }
    for(int i=N-2;i>=0;i--){
        if(data[i].num>min)
            data[i].f2=false;
        else
            min=data[i].num;
    }
    vector<int> result;
    for(int i=0;i<N;i++){
        if(data[i].f1==true && data[i].f1==data[i].f2)
            result.push_back(data[i].num);
    }
    printf("%d\n",result.size());
    sort(result.begin(),result.end());
    for(auto it1=result.begin();it1!=result.end();it1++)
        printf("%d%c",*it1,it1+1==result.end()?'\n':' ');
    if(result.size()==0)
    printf("\n");
}

上一篇: PAT 1045 快速排序

下一篇: PAT1045