【洛谷】P1138 第k小整数

待我称王封你为后i 2022-09-07 06:11 56阅读 0赞

# 题目 #

求出某串数字的第k小整数。

# 思想 #

*  使用快速排序

# 代码 #

#include<iostream>
    using namespace std;
    
    const int maxN = 10005;
    int arr[maxN];
    //使用快排 
    int partition(int left,int right){ 
    	int pivot_key = arr[left];//临时存储pivot_key
    	while(left < right){ 
    		while(left < right && arr[right] >= pivot_key){ 
    			right--;
    		}
    		arr[left] = arr[right];
    		while(left < right && arr[left] <= pivot_key){ 
    			left++;
    		}
    		arr[right] = arr[left]; //正是因为这些赋值，才使得下次的while得以绕过
    	} 
    	arr[left] = pivot_key; 
    	return left;//最后要返回的分界点 
    }
    
    void quick_sort(int left,int right){ 	
    	if(left >= right){ 
    		return;
    	}
    	int mid = partition(left,right);
    	quick_sort(left,mid-1);
    	quick_sort(mid+1,right);
    }
    
    int main(){ 
    	int n , k;
    	cin >> n >> k;
    	for (int i = 0;i< n;i++)
    		cin >> arr[i];
    	
    	quick_sort(0,n-1);		
    	
    	//找出第k小的数 
    	int pre = arr[0]; 
    	int cnt = 1;
    	if (k == 1){ 
    		cout << pre;
    		return 0;
    	}
    	int i ;
    	for (i = 1;i < n;i++){ 
    		//cout << arr[i]<<" ";
    		if (arr[i] != pre){ 
    			pre = arr[i];
    			cnt ++;
    			if (cnt == k){ 
    				cout << arr[i]<<"\n";
    				return 0;
    			}
    		}
    	}
    	if (i==n){ 
    		cout << "NO RESULT";
    	}
    }
    /* 9 3 3 3 7 2 5 1 2 4 6 */

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷——P1423 小玉在游泳

P1423 小玉在游泳题目描述小玉开心的在游泳，可是她很快难过的发现，自己的力气不够，游泳好累哦。已知小玉第一步能游2米，可是随着越来越累，力气越来越小，她接下

比眉伴天荒/ 2023年10月02日 05:22/ 0 赞/ 14 阅读

相关洛谷P1421 小玉买玩具

咳咳，从新手村开讲，以后会不定时的讲别的章节本章讲解：小玉买文具题目描述班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是1元9角

布满荆棘的人生/ 2023年07月07日 03:34/ 0 赞/ 11 阅读

相关【洛谷】P1576 最小花费

前言文章来源：CSDN@LawsonAbs 合理时间：12min -------------------- 题目 [题目链接][Link 1]

骑猪看日落/ 2022年09月09日 09:12/ 0 赞/ 188 阅读

相关【洛谷】P1138 第k小整数

题目求出某串数字的第k小整数。思想使用快速排序代码 include<iostream> using namespace st

待我称王封你为后i/ 2022年09月07日 06:11/ 0 赞/ 57 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 335 阅读

相关洛谷P1164 小A点菜

题目背景 uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。 uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。题

曾经终败给现在/ 2022年05月28日 07:10/ 0 赞/ 190 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 334 阅读

相关洛谷P2709 小B的询问

莫队模版本来想能不学莫队就不学，但是这次比赛被莫队卡得好惨，于是学了一发。。先切道模板题。。最普通的莫队就是把序列分块，然后按照询问所在的块来排序，减少指针的移

矫情吗；*/ 2022年01月07日 05:19/ 0 赞/ 229 阅读

相关最小生成树 & 洛谷P3366【模板】最小生成树 & 洛谷P2820 局域网

嗯... 理解生成树的概念：在一幅图中将所有n个点连接起来的n-1条边所形成的树。最小生成树：边权之和最小的生成树。最小瓶颈生成树

迈不过友情╰/ 2021年12月10日 20:03/ 0 赞/ 318 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 458 阅读