分析: 看见题目中有lg(n) 项,首先应该想到的是分治法,算法的思路如下:(为简单起见,不考虑取整的问题)
将 n 个元素分成 n/2 对.每一对之间互相比较.这样一共比较了 n/2 次.然后将每一对的较小元素放在 S[1...n/2] 数组中,较大的元素对应的放在 B[1...n/2]中.显然最小的元素肯定在数组S中,那么第2小的元素(设代号为X) 是否也在 S 中呢?
首先,假设第2小元素X在数组S 中,因为最小的元素也在数组S中,所以X在S中同样也肯定是第2小元素.这样我们可以递归的在S中继续寻找第2小元素,并将搜索的范围缩小了一半.
如果第2小元素X不在数组S中,(即在数组B中),由上面的分区算法知,在B中的元素必然大于相应位置上S中的元素.在这里X是第2小元素,它仅大于最小元素.所以它在B中的位置与最小元素在S中的位置相同.
综上可知:第2小元素X要么是S中的第2小元素,要么是B中位置与最小元素在S中的位置相同的元素.
这样算法就很明了了: 将 n 个元素分成 n/2 对比较,较大者放入B,较小者放入S,若B和S的大小为1,则B[1]作为第2小元素返回,S[1]作为最小元素返回(主要是想得到最小元素在S中的位置),若B和S的大小大于1,则递归的在S中寻找最小元素和第2小元素,并将S中得到的第2小元素与B中位置与最小元素在S中的位置相同的元素相比较(有点拗口),其中较小者便是真正的第2小元素.
举个例子吧,如: 在序列 3,2,5,8,6,4,9,7 中寻找第2小元素.
过程:首先分在[3,2] [5,8] [6,4] [9,7] 四组,经比较后得到 S1=2,5,4,7 B1=3,8,9,7.
再将 S1分区,得到 S2=2,4 B2=5,7 .
S2中最小值是2,第2小元素是4. B2中与S2中最小值对应的是5,因4小于5.所以得到S1的最小值是2,第2小元素是4, 在B1中与S1中最小值2对应的是3,因4>3,所以得到 整个序列的第2小元素为 3.完成.
算法分析: T(n)=n/2+T(n/2)+1 //其中的n/2是分区时比较的次数,1 是递归时S中得到的第2小元素与B中位置与最小元素在S中的位置相同的元素相比较的消耗.
T(2)=1.
解递归式即可:T(n)=n+lg(n)-2 .
另解:
相关推荐
【问题描述】每次都是优化选出一个元素(分组后的中位数)为划分基准,在线性时间内寻找第i小元素。提示:分组时的组的个数为n/5的向下取整;分组后的中位数取第(num_group/2向上取整)小的元素。 【输入形式】在...
找中值和第k小元素,找出A[1...N]中第k小元素.找第K小元素 需要找中位数: 如果有偶数个,则找第n/2或n/2+1个小元素则可找到中位数; 如果有奇数个,则找第n/2+1个小元素则可找到中位数。
实现并验证合并排序算法; Ex2:实现并验证快速排序算法 Ex3:用递归与分治的方法设计并实现寻找第k小元素算法
本文实例讲述了Go语言算法之寻找数组第二大元素的方法。分享给大家供大家参考。具体如下: 该算法的原理是,在遍历数组的时,始终记录当前最大的元素和第二大的元素。示例代码如下: 代码如下:package demo01 ...
用快速排序的方法寻找序列中第k小的元素,算法课后练习题,分治的思想
c语言实现取数组中的第2大值
递归与分治(二)__刘汝佳_黑书_课件_经典.ppt
然后我们从第二个元素开始扫描列表,找到最后n-1个元素中的最小元素,再和第二个元素交换位置,把第二小的元素放在它的最终位置上。一般来说,在对该列表做第i遍扫描的时候(i的值从0到n-2),该算法在最后n-i个元素中...
定义一维数组,包含10个元素,分别赋随机整数,然后求出第二大值,第二小值,并输出下标。 备注:可以求其他值的下标和大值小值,还可以输出原下标和排序后的下标,自己改一下就行。。记得改一下包名类名
寻找主元素leetcode LeetCode-问题 # 问题标题 问题 解决方案 1. 二和 2. 字符串中的第一个唯一字符 3. 有序数组的平方 4. 从排序数组中删除重复项 5. 查找数组中所有消失的数字 6. 查找数组中的所有重复项 7. 多数...
FIND_NDIM 沿维度查找第一个/最后一个非零元素索引。 I = FIND_NDIM(BW,DIM) 返回第一个非零的下标BW 沿维度 DIM 的元素。 输出 I 将包含零找不到非零元素的元素位置 I = FIND_NDIM(BW,DIM,'first) 与 I = FIND_...
014 求解二维数组的最大/最小元素 015 利用数组求前n个质数 016 编制万年历 017 对数组元素排序 018 任意进制数的转换 019 判断回文数 020 求数组前n元素之和 021 求解钢材切割的最佳订单 022 通过指针比较...
[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ,首先需要在单链表中寻找到第i-1个结点并用指针p指示,然后申请一个由指针s 指示的结点空间,并置x为其数据域值,最后修改第i-1个结点,并使...
问题描述 对于给定整数数组a[],寻找其中最大值,并返回下标。 输入格式 整数数组a[],数组元素个数小于1等于100。...第二行为数组的各个元素。 输出格式 输出最大值,及其下标 样例输入 3 3 2 1 样例输出 3 0
第二部分 工 具 篇 第3章 OSX工具集 25 3.1 class-dump 25 3.2 Theos 27 3.2.1 Theos简介 27 3.2.2 安装Theos 28 3.2.3 Theos用法介绍 30 3.2.4 Theos开发tweak示例 51 3.3 Reveal 53 3.4 IDA 57 3.4.1...
通过比较当前元素与最大值和第二大值的大小关系,来更新相应的变量。 2.将一次比较视为一场比赛。在一次比较中,认为小的数是被淘汰的。如果在寻找最大数的顺序比较过程中,逐次记录下被当前最大数所淘汰的数。那么...
C语言实例解析精粹(第二版) 光盘代码 本文件包括以下内容: ※ 1、文件说明 ※ 2、源码操作说明 ※ 3、光盘目录清单 ◎ 源码操作说明 源代码使用方法是(以实例1为例): 将该实例的源码,比如实例1的1.c文件(可以...
寻找主元素 leetcode 既然来到这里 那就认真的读下去吧 放下浮躁 放下心 去认真读 请谨记 没有立即的成功 只有不懈的努力 少点功利心 多点奋斗(More interest Less interests) 勿骄勿燥 这里有go的数据结构和一些...