Jorbe's Blog

题目描述：

查找一个数组的第K小的数，注意同样大小算一样大。
如  2 1 3 4 5 2 第三小数为3。

输入：

输入有多组数据。
每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。

输出：

输出第k小的整数。

样例输入：

6
2 1 3 5 2 2[......]

题目描述：

输入数组长度 n
输入数组      a[1...n]
输入查找个数m
输入查找数字b[1...m]

输入：

输入有多组数据。
每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m<=n<=100）。

输出：

如果在n个数组中输出YES[......]

这几天闲来无事，又翻了翻《挑战程序设计竞赛》。这本书其实是去年年初的时候买的，到现在将近一年了吧。说来惭愧，到现在还没看完。
昨天一翻就翻到了贪心法这一小节。贪心法一直是算法设计中经常用到的一种方法。比如，最小生成树算法(prim algorithm)和最短路径算法(dijkstra algori[......]

题目说明：
时间限制:2000ms
单点时限:1000ms
内存限制:256MB

描述

L国是一个有着优美景色且物产丰富的国家，很多人都喜欢来这里旅游并且喜欢带走一些纪念品，大神同学也不例外。距离开L国的时间越来越近了，大神同学正在烦恼给她可爱的小伙伴们带什么纪念品好，现在摆在大神[......]

求第K小的数

一般的方法是：先对数列进行一次排序，然后找到第k小的数。假如用快排来做排序的话，时间复杂度为O(nlogn)。O(nlogn)看起来貌似效果也不错，但是否还有比它更高效的算法呢？答案是肯定的。我们先来看下第k小的数有什么特点：一个数列中第k小的数，在这个数列中一定有k-1个数比它小，[......]