动象论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 192 | 回复: 26

经典题-第k小的数

[复制链接]

4

主题

30

帖子

54

积分

清正廉明~版主

Rank: 16Rank: 16Rank: 16Rank: 16

积分
54

论坛官方

发表于 2020-7-13 15:13:10 | 显示全部楼层 |阅读模式
本帖最后由 -墟- 于 2020-7-13 15:15 编辑

题目描述
给定一个长度为n(1≤n≤5000001)的无序正整数序列,以及另一个数k(1≤k≤n)(关于第k小的数:例如序列{1,2,3,4,5,6}中第3小的数是3。)
输入
第一行两个正整数n,k。
第二行为n个正整数。
输出
第k小的数。
样例输入6 3
1 2 3 4 5 6
样例输出
3
HELLO,我是 -墟- ,一名蒻到不能再蒻的超级蒟蒻

4

主题

30

帖子

54

积分

清正廉明~版主

Rank: 16Rank: 16Rank: 16Rank: 16

积分
54

论坛官方

 楼主| 发表于 2020-7-13 15:14:15 | 显示全部楼层
本帖最后由 -墟- 于 2020-7-13 15:16 编辑

有思路的大佬可以把代码发到评论区,明天发解析版の代码(我太懒了拖到明天)
HELLO,我是 -墟- ,一名蒻到不能再蒻的超级蒟蒻
回复

使用道具 举报

12

主题

94

帖子

227

积分

清正廉明~版主

风纪委员

Rank: 16Rank: 16Rank: 16Rank: 16

积分
227

论坛官方最佳新人活跃会员

发表于 2020-7-15 11:29:08 | 显示全部楼层
  1. #include<iostream>
  2. using namespace std;
  3. int main(){
  4.     int n,k;
  5.     cin>>n>>k;
  6.     int a[n];
  7.     int b[k];
  8.     for(int i=0;i<k;i++){
  9.         b[i]=5001;
  10.     }
  11.     for(int i=0;i<n;i++){
  12.         cin>>a[i];
  13.     }
  14.     int i=0;
  15.     while(i<n){
  16.         //cout<<i<<endl;
  17.         for(int j=0;j<k;j++){
  18.             if(b[j]>=a[i]){
  19.     for(int p=k-1;p>j;p--){
  20.                     b[p]=b[p-1];
  21.                 }
  22.                 b[j]=a[i];
  23.                 break;
  24.        }
  25. }
  26. i+=1;
  27.     }
  28.     cout<<b[k-1]<<endl;
  29.     return 0;
  30. }
复制代码

五星好评走一波~~~~~

评分

参与人数 1 +200 收起 理由
admin + 200 赞一个!

查看全部评分


tel:181 5707 6602
回复

使用道具 举报

4

主题

30

帖子

54

积分

清正廉明~版主

Rank: 16Rank: 16Rank: 16Rank: 16

积分
54

论坛官方

 楼主| 发表于 2020-7-15 15:13:58 | 显示全部楼层
实属惨烈
HELLO,我是 -墟- ,一名蒻到不能再蒻的超级蒟蒻
回复

使用道具 举报

4

主题

30

帖子

54

积分

清正廉明~版主

Rank: 16Rank: 16Rank: 16Rank: 16

积分
54

论坛官方

 楼主| 发表于 2020-7-15 15:15:08 | 显示全部楼层
本帖最后由 -墟- 于 2020-7-15 15:22 编辑

这道题其实就是快速选择。看看n的大小,5000000,就算先sort一遍还是TLE,这个时候就应该从快排的角度去思考。每一次都会将k所在的位置的范围缩小,时间复杂度也是比快排还要低的(懒得估)。标准答案
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, k, a[5000001];

  4. void read() { //快读,一定要用
  5.         char ch;
  6.         ch = getchar();
  7.         int f;
  8.         for(int i = 0; i < n; i++) {
  9.                 f = 1;
  10.                 while(ch < '0' || ch > '9') {
  11.                         if(ch == '-')
  12.                                 f = -1;
  13.                         ch = getchar();
  14.                 }
  15.                 while(ch >= '0' && ch <= '9') {
  16.                         a[i] = a[i] * 10 + ch - '0';
  17.                         ch = getchar();
  18.                 }
  19.                 a[i] *= f;
  20.         }
  21. }

  22. int partition(int l, int r) { //用快排的方法,左边的永远大于右边的
  23.         int pivot = a[l], left = l + 1, right = r;
  24.         while(left <= right) {
  25.                 while(left <= right && a[left] <= pivot) {
  26.                         left++;
  27.                 }
  28.                 while(left <= right && a[right] > pivot) {
  29.                         right--;
  30.                 }
  31.                 if(left < right) {
  32.                         swap(a[left], a[right]);
  33.                 }
  34.         }
  35.         swap(a[l], a[right]);
  36.         return right;
  37. }

  38. int quickSelect(int l, int r, int k) { //如果第k个在左边就只在左边进行下一轮,在右边就在右边进行,正好是partition返回值则返回这个数
  39.         if(l == r) {
  40.                 return a[l];
  41.         }
  42.         int p = partition(l, r);
  43.         if(p == k - 1) {
  44.                 return a[p];
  45.         }else if(p < k - 1) {
  46.                 return quickSelect(p + 1, r, k);
  47.         }else {
  48.                 return quickSelect(l, p - 1, k);
  49.         }
  50. }

  51. int main() {
  52.         scanf("%d%d", &n, &k);
  53.         read();
  54.         cout << quickSelect(0, n - 1, k);
  55.         return 0;
  56. }
复制代码
HELLO,我是 -墟- ,一名蒻到不能再蒻的超级蒟蒻
回复

使用道具 举报

4

主题

30

帖子

54

积分

清正廉明~版主

Rank: 16Rank: 16Rank: 16Rank: 16

积分
54

论坛官方

 楼主| 发表于 2020-7-15 15:24:33 | 显示全部楼层
黄蕊小白花 发表于 2020-7-15 11:29
五星好评走一波~~~~~

20分,TLE了
HELLO,我是 -墟- ,一名蒻到不能再蒻的超级蒟蒻
回复

使用道具 举报

12

主题

94

帖子

227

积分

清正廉明~版主

风纪委员

Rank: 16Rank: 16Rank: 16Rank: 16

积分
227

论坛官方最佳新人活跃会员

发表于 2020-7-15 18:36:15 来自手机 | 显示全部楼层
-墟- 发表于 2020-7-15 15:24
20分,TLE了

20分是高是低
动象论坛欢迎您!文明发帖,理性交流!(๑`・ᴗ・´๑)
回复

使用道具 举报

138

主题

1042

帖子

2914

积分

清正廉明~管理员

用心做好论坛,用心创造精品!

Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20

积分
2914

论坛官方最佳新人活跃会员热心会员推广达人宣传达人灌水之王突出贡献优秀版主荣誉管理论坛元老论坛财主在线王比特币王

发表于 2020-7-15 19:37:30 | 显示全部楼层

10个点,只过了2个,7个不过,不行哦
估计是超了时、过了内存或者不符合规定
动象论坛
点滴纯粹 简单自然
动象论坛,用心做好论坛!用心创造精品!
[点我进入]dxbbs.twxne.top
回复

使用道具 举报

55

主题

267

帖子

687

积分

清正廉明~版主

致敬·Mozilla Firefox

Rank: 16Rank: 16Rank: 16Rank: 16

积分
687

论坛官方最佳新人活跃会员

发表于 2020-7-15 19:38:10 | 显示全部楼层
本帖最后由 Mozilla 于 2020-7-15 19:41 编辑
-墟- 发表于 2020-7-13 15:14
有思路的大佬可以把代码发到评论区,明天发解析版の代码(我太懒了拖到明天) ...

写好了,并且优化了输出和速度。但是python由于要不停滴判断数据类型(还有其他原因),速度从根本上就比C++慢,所以对python的时限应该要放宽。
  1. n=int(input('输入你的n'))
  2. k=int(input('输入你的k'))

  3. num=[]

  4. for i in range(n):
  5.         num1=int(input('输入你的第%s个数'%n))
  6.         n-=1
  7.         num.append(num1)


  8. def bubble(num2):
  9.     for j in range(len(num2)-1):
  10.                
  11.         for i in range(len(num2)-1):
  12.             if num2[i]<num2[i+1]:
  13.                 num2[i+1],num2[i]=num2[i],num2[i+1]



  14. bubble(num)
  15. print(str(num[k-1]))
复制代码

评分

参与人数 1 +200 收起 理由
admin + 200 编程大师I!

查看全部评分

动象论坛欢迎您!文明发帖,理性交流!(๑`・ᴗ・´๑)
回复

使用道具 举报

138

主题

1042

帖子

2914

积分

清正廉明~管理员

用心做好论坛,用心创造精品!

Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20

积分
2914

论坛官方最佳新人活跃会员热心会员推广达人宣传达人灌水之王突出贡献优秀版主荣誉管理论坛元老论坛财主在线王比特币王

发表于 2020-7-15 19:48:16 | 显示全部楼层
Mozilla 发表于 2020-7-15 19:38
写好了,并且优化了输出和速度。但是python由于要不停滴判断数据类型(还有其他原因),速度从根本上就比C ...

速度还得拿上去遛遛,才知道过不过
动象论坛
点滴纯粹 简单自然
动象论坛,用心做好论坛!用心创造精品!
[点我进入]dxbbs.twxne.top
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

 QQ 手机版小黑屋网站地图

GMT+8, 2021-7-25 07:04 Processed in 0.169970 second(s), 26 queries .

CopyRight © 2020-2021 DongXiang BBS. All Rights Reserved.

ICP备案号:粤ICP备17035028号-1

Sectigo签章 MySSL签章

快速回复 返回顶部 返回列表