这个题目的一种思路是利用快排思想来解决,可以达到O(nlogn)的时间效率。
详细代码如下:
/*
* 在一列数中寻找第k大的数,使用快排思想,一趟快排后会返回一个基准点的位置,如果该位置loc正好处于
* 要求的第k个数的位置,则该位置的数即为所求;如果loc>k,说明要求的第k大的数,在左边子数组中,如果loc<k,
* 则要求的数为右边子数组的第k-loc个位置的数
*/
public class Findnth {
public static void main(String args[]){
int array[] = {5, 6, 7, 9, 8, 4, 3, 2, 1, 10, 12, 11, 13, 14, 15, 16, 17, 19, 18, 20} ;
int re=select(array,0,array.length-1,15);
System.out.println("第---小的数是:"+re);
}
public static int select(int a[],int left,int right,int k){//求第k小的数
if(left==right){
return a[left];
}
int loc=partition(a,left,right);//返回一趟快排后某个基准点的位置
int kth=loc-left+1;//该基准数在当前的子数组中是第几小的数
if(k==kth){//如果该趟排序后返回的基准位置所处的位置正好是这个子数组的第k小的数
return a[loc];//返回处于该位置的值就是要求的第k小的数
}else if(k<kth){
return select(a,left,loc-1,k);//求左边子数组中的第k小的数
}else{
return select(a,loc+1,right,k-kth);//求右边子数组中的第k-kth小的数
}
}
public static int partition(int a[],int left,int right){
//一趟快排,返回以a[left]为基准点的位置
int temp=a[left];
while(left<right){
while(left<right&&a[right]>=temp){
right--;
}
a[left]=a[right];
while(left<right && a[left]<=temp){
left++;
}
a[right]=a[left];
}
a[left]=temp;
return left;
}
}
分享到:
相关推荐
C语言程序设计-求一个四位数的各位数字的立方和.c
若填入的数字在第一行(不在第n列),则下一个数字在第n行且列数加1 * 3.若填入的数字在该行的最右侧,则下一个数字就填在上一行的最左侧 * 4.一般地,下一个数字在前一个数字的右上方(行数少1,列数加1) * 5....
列出所有数字1到数字n的连续自然数的排列,要求所产生的任一数字序列中不允许出现得复数字。 Input 输入:n(1) Output 由1~n组成的所有不重复的数字序列,每行一个序列。 Sample Input 3 Sample Output 1 2 3 1 ...
条件二:如果文件二里面B列里的单位名称=文件一里B列的单位名称,那么就把文件二中这个单位在E列和F列中的数字取到文件一中同一单位名称下的J列和K列,进行累计;条件三:如果文件二中含有文件一中没有的 单位名称,...
对于输入结点,则判断当前点是否在第一个输出端触点。 对于输出结点,则判断当前点是否在第一个输入端触点。 输入结点和输出结点的这样判断,一眼看上去似乎反了,但实际上有利于整个程序的编写。可以简单地这样分类...
输入4个数字(1~10),则列出所有可能计算结果为24的方案。要求: 方案不能重复(加法乘法交换律等算不同方案)。 计算中局部可以为分数,结果为整数即可(如 3 3 7 7 算法: (3 + 3/7)*7) 如果没有找到方案...
显示电路采用4位共阴极LED数码管,从B口输出段码,列扫描用K口来实现。 由于采用了改进型智能温度传感器DS18S20作为检测元件,与传统的温度计相比,本数字温度计减少了外部的硬件电路,具有低成本和易使用的特点。...
这点可能是从DiscJuggler学来的 ③在第一贴中提到的生成的di映像文件功能就是这个按钮了,除了Record DiscImage和Erase Disc外其它的刻录动作中都有这个按钮 ④对RW可擦写光盘,选中此项可在刻录前先擦除光盘上的...
(29)某公司在传输数据过程中为了安全要对数据进行加密,若传递的是四位的整数,对其进行加密的规则为:每位数字都加上5,然后用和除以10的余数代替该数字,再将第一位和第四位交换,第二位和第三位交换。...
3.5.9 WEEKNUM——返回日期在一年中是第几周 144 3.5.10 ISOWEEKNUM——返回日期在一年中的ISO周数 145 3.5.11 WORKDAY——计算与指定日期相隔数个工作日的日期 146 3.5.12 WORKDAY.INTL——计算与指定日期相隔...
这是MATLAB的语句吧,意思是在一个2行3列共6个子图的图中,定位第1个图来进行操作(画图)。最后面那个1表示第1个子图。 那个数字的变化来定位不同的子图 figt(t7); title('待试数字7') subplot(2,3,3); figt(t4); ...
下面给出一个例子:选中一列,然后单击“格式”菜单中的“单元格”命令,在弹出的对话框中选择“数字”选项卡,在“分类”列表中选择“自定义”,然后在“类型”文本框中输入“"正数:"($#,##0.00);"负数:"($ #,##...
题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和等于该数本身。例如: 153是一个"水仙花数",因为153=1的三次方+5的三次方+3的三次方。 1.程序分析:利用for循环控制100-999个...
标签与数字文件相对应,因此labels.txt的第一行是digit.txt第一行中数字的标签。 培训和测试图像将包含在bigbangtheory子目录中(由于限制,我没有在此处上传这些图像,如果您需要这些图像,请随时给我发送电子邮件...
给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。 示例: 输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2 解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k ...
=100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态,0表示金币正面朝上,1 表示背面朝上。 金币阵列游戏的规则是: (1)每次可将任一行金币翻过来放在原来的...
使用加减乘除,第一个能得出24者为赢。(其中,J代表11,Q代表12,K代表13,A代表1),按照要求编程解决24点游戏。 基本要求: 随机生成4个代表扑克牌牌面的数字字母,程序自动列出所有可能算出24的表达式,用擅长的...
题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个"水仙花数",因为153=1的三次方+5的三次方+3的三次方。 1.程序分析:利用for循环控制100-999个数,...
在广义真值表中,与每个数字相关联的基数是任意的。 这允许详尽地生成异构基数变量的组合; 例如,我们可能会考虑头发和眼睛颜色的每一种可能组合,使用{黑色、棕色、金发、灰色、红色}中的头发颜色和{棕色、蓝色、...
在接收文件的时候,很多情况下是以4096字节附近的整行数字节为一次刷新界面显示。 10.串口的设置 在设置串口的时候,可能有些选项不能设置,这与计算机的本身限制有关。一般都支持115200bps。 11.命令发送框内的...