http://blog.csdn.net/yanzi1225627/article/details/8111806、http://www.eyeandroid.com/thread-9629-1-1.html这里讨论了求第二大的思路。现在研究如果是第i大怎么办?
先清晰一下概念,如果有个数组a[6] = 2 60 10 32 84 6; 那么第1大的数是最大值84, 第2大是60, 第3大是32, 第1小是2, 第二小是6., 第三小是10, 第4小是32. 也即如果让找第i小, 等价于找第n-i+1大。 如果让找第i大, 等效于找第n+1-i小,两者可以互换。
思路还是快速排序,为了方便我们假设找第i小的数。
先看快速排序的partition函数:
int partition(int a[], int i, int j)
{
int pivot = a[i];
while(i<j)
{
while(i<j && a[j] >= pivot)
j--;
if(i<j)
a[i++] = a[j];
while(i<j && a[i] <= pivot)
i++;
if(i<j)
a[j--] = a[i];
}
a[i] = pivot;
return i;
}
下面就是找第i小的数:
int find_n_min(int a[], int low, int high, int n_min)
{
int p = partition(a, low, high);
if(p-low+1 == n_min)
return a[p];
if(p-low+1 > n_min)
return find_n_min(a, low, p-1, n_min);
else
return find_n_min(a, p+1, high, n_min-(p-low+1));
}
解释下思路,先找到划分的基准索引p,p左边的都是小于a[p]的, 那么可以得到a[p]就是第p-low+1小的数。 为了方便举个例子, 如果经过一次partition函数之后,数组为 5 3 6 12 50 21,p = 3,也就是a【3】 = 12是划分的基准,那么a【3】肯定是3-0+1 = 4,第4小的数。
如果p-low+1 >n_min, 比如,p-low+1 = 5, a[p]是第5小的数,而程序让找第2小的数,这个时候需要递归到 【low, p-1】区间去找第2小的数,这个举了例子应该不难理解了。
对应的如果小于n_min的话,就要从p+1开始到high区间进行调用搜索第n_min - (p - low +1)小的数。
这里需要注意两个事,
第一,递归的时候前面不要忘了return
第二,递归的时候新的区间一定是【low, p-1】,这个减一一定不能少!为什么?这是我们这里采用的a[low]作为基准值,而http://blog.csdn.net/yanzi1225627/article/details/8109035这里采用的是(high
+ low)/2作为基准值,所以递归的时候,临界区间的一边没有减一。
为了清晰说明这个问题,我们举个例子,假设初始数组a[] = 12 3 6 5 50 21,我们要找第3小的数。
第一次进到partition函数后,以12作为基准,partition函数返回的p = 3,数组这个时候更新成5 3 6 12 50 21,因为p-0+1 = 4大于3,所以索引从0到2搜索即可!如果上面临界区间没有减1,也就是从0到3搜索的话(数组为5 3 6 12),我们看看会有啥后果?
第二次进到partion,基准为5,函数返回的p = 1,数组更新成3 5 6 12,由于p-0+1 = 2,因此需要进到第三次partition,临界区间不加1的话(正确的应该从p+1开始),就是从p(也就是1)到3,数组为 5 6 12,问题转换为在5 6 12中找第1小的数
第三次进到partion,坏就坏在这,因为是用的第一个数5作为基准的,所以这个partition返回的p = 1. 也就是5,所以最终函数的找到的第三小的数也就是5.这显然是错误的!因此,在这里用a[low]作基准的话,临界区间必须减1。如果像这里http://blog.csdn.net/yanzi1225627/article/details/8109035用mid
= (low +high)/2坐的基准,更新后的区间则不用减一。
至此,在数组中找第i小的问题解决了,如果要找第i大的数只需将参数转化下就中,这在开头交代过。或者将上面函数里的p-low+1 改成high-p+1,a[p]为第i大的数,简单调整下即可。
分享到:
相关推荐
用递归算法编写求一个数组A中的最大元素;/****一个递归算法,求数组A中最大的元素***/ #include int Max(int A[], int i, int j) //求顺序表A中的最大元素 ……
从数组1的尚未比较的元素中拿出第一个元素array1(i),用array1(i)与array2(j)进行比较(其中j>i且j的长度),可能出现下面两种情况, 1. 数组2中找到了一个与array1(i)相等的元素,则将array2(j)与array2(i)进行...
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。
System.out.println("最小值是数组中的第"+minindex+"个数"); //输出七个数中的最大值 int maxindex=0; //定义变量minindex并赋初值用于保存最大值的下标 int max; //定义max并赋初值为0,设做是...
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元 素的情况下,该数组能否变成一个非递减数列。非递减数列定义如下:对 于数组中所有的 i (1 <= i ),满足 array[i] [i + 1]
给你一个整数数组 nums,返回数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法,...
西南交通大学算法分析与设计hhy实验4.2编写一个分治算法来搜索mx n矩阵matrix中的一个目标值target,该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。 4.1.1该问题的自然语言描述法 ...
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
最近在工作碰到一个问题,就是用javascript求数组中所有数字能拼接出的最大整数,数组的每一项为单独的拼接项,不能再拆开,例如[2,34]中2和34分别为要被拼接的数字,而不是说34还能继续拆分为3和4。 具体需求为,...
试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。 2.在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并...
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
本文实例讲述了php数组冒泡排序算法。...$j++){//需要比较$len-1次,因为循环到最后一个数时,后面没有数可以比较了,所以循环到倒数第二个数正好 $k=$j+1;//得到当前数的后一个数的下标,我们依次比较的是数组
1. 求一维数组中的最大[小]值 2. 求一维数组中的总和,平均值 3. 添加,删除,修改,搜索等 具体请参考本人FTP\\5.0S1\\JAVA\\数组完整操作范例。[重复让人如此崩溃!] 二维数组 1. 定义:省略 2. 用法:...
数组和广义表 一、实验名称:数组和广义表 二、实验目的: (1)熟悉C语言的上机环境,进一步掌握C语言的结构特点; (2)掌握线数组和广义表储存结构的...假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点。
本文实例讲述了C#求数组中元素全排列的方法。分享给大家供大家参考。具体如下: 1.算法描述 全排列的第一项是该数组的升序排列,最后一项是该数组的降序排列。本文中用到的了一个函数FindNextArray:从升序排列开始...
软件的基本功能:本软件在 vs code 环境下实现先来先服务、短作业优先、高响应比优先、时间片轮转调度算法、优先级调度算法和多级反馈队列调度算法,满足不同需求调度。 输入/输出形式:I/O 输入:data 数组键盘输入...
银行家算法分配资源的原则是:系统掌握每个进程对资源的最大需求量,当进程要求申请资源时,系统就测试该进程尚需资源的最大量,如果系统中现存的资源数大于或等于该进程尚需求资源最大量时,就满足进程的当前申请。...
第4章:算法 第5章:选择结构 第6章:循环结构 第7章:函数 第8章:预处理命令 第9章:指针 第10章:数组 第11章:数组,结构体,共同体 第12章:面向对象 第13章:面向对象2 第14章:继承 第15章:多态,动态类型和...