首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1045 快速排序 (25 分)

1045 快速排序 (25 分)

作者头像
韩旭051
发布2019-11-08 00:59:33
4090
发布2019-11-08 00:59:33
举报
文章被收录于专栏:刷题笔记刷题笔记

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://cloud.tencent.com/developer/article/1535034

1045 快速排序 (25 分)

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

卡在第二个测试点,是输出0个的情况,最后加一个回车就过了。。。

第一次写的原生代码,活生生写了三次for循环,可以简化掉

输入进来,正反各循环一次,记录i个数据左边最大值,和i右边最小值,只要 第i个数据比最大值大,最小值小就是关键元素

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>num(n);
	vector<int>numax(n);
	vector<int>numin(n);
	
	int max=-1,min=1000000009;
	for(int i=0;i<n;i++){
		cin>>num[i];
		if(num[i]>max)max=num[i];
		numax[i]=max;
	}
	for(int i=n-1;i>=0;i--){
		if(num[i]<min)min=num[i];
		numin[i]=min;
	}
	int count=0;
	for(int i=0;i<n;i++){
		if(num[i]<=numin[i]&&num[i]>=numax[i]){
			count++;
		}
	}
	
	cout<<count<<endl;
	int flag=0;
	int cou=count;
	vector<int>num3(count);
	for(int i=0;i<n;i++){
		if(num[i]<=numin[i]&&num[i]>=numax[i]){
			num3[count-1]=num[i];
			count--;
			//cout<<num3[count];
		}
	}
	sort(num3.begin(),num3.end());
	for(int i=0;i<cou;i++){
			if(flag){
				cout<<" ";
			}flag=1;
			cout<<num3[i];
		
	}
    cout<<endl;
	return 0;
} 

代码还是要看柳神的

1.原来柳神也用了好几次for循环

2.每个数不超过 10​的九次方,int也撑下了。

柳神的分析

分析:对原序列sort排序,逐个比较,当当前元素没有变化并且它左边的所有值的最大值都比它小的时候就可以认为它一定是主元(很容易证明正确性)~ 如果硬编码就直接运行超时了…后来才想到这种方法~ 一开始有一个测试点段错误,后来才想到因为输出时候v0是非法内存,改正后发现格式错误(好像可以说明那个第2个测试点是0个主元?…)然后加了最后一句printf("\n");才正确(难道是当没有主元的时候必须要输出空行吗…)

#include <iostream>
#include <algorithm>
#include <vector>
int a[100000], b[100000], v[100000];
using namespace std;
int main() {
    int n, max = 0, cnt = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        if(a[i] == b[i] && b[i] > max)
            v[cnt++] = b[i];
        if (b[i] > max)
            max = b[i];
    }
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++) {
        if (i != 0) printf(" ");
        printf("%d", v[i]);
    }
    printf("\n");//不加这句会有一个测试点没法通过。.
    return 0;
}

这道题,比较迷,不知道为啥加\n 考试的时候错了记得这样测试一下行了。。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-08-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1045 快速排序 (25 分)
    • 输入格式:
      • 输出格式:
        • 输入样例:
          • 输出样例:
          • 卡在第二个测试点,是输出0个的情况,最后加一个回车就过了。。。
            • 第一次写的原生代码,活生生写了三次for循环,可以简化掉
              • 1.原来柳神也用了好几次for循环
          • 输入进来,正反各循环一次,记录i个数据左边最大值,和i右边最小值,只要 第i个数据比最大值大,最小值小就是关键元素
          • 代码还是要看柳神的
          • 2.每个数不超过 10​的九次方,int也撑下了。
          • 柳神的分析
          • 这道题,比较迷,不知道为啥加\n 考试的时候错了记得这样测试一下行了。。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档