博客分类：
我们在讨论求一个数组中最小的元素时，相对来说很简单，也很容易找到一个高效率的办法。在一些特殊的情况下甚至还可能有更加优化的方法。如果再把这个问题再深入一点。比如说，我们要求第二小的元素，那么有没有足够高效率的方法呢？
在我们思考这个问题的时候，书上的有一个问题就是要求我们来验证在n个元素里，在最坏情况下找到第二小的元素需要经过n + lgn - 2次的比较。那么，我们能不能找到这么一种办法呢？先理一下大致的思路。
这种办法相对比较简单直接，就是第一次遍历找到最小的元素。然后在剩下的集合里找最小的那个。这样就找到了第二小的。这种方法在最坏情况下的具体比较次数是n - 1 + n - 2 = 2n -3。很显然，虽然这是一个可以达到O(n)级别的方法。但是如果以问题中n + lgn - 2的标准来衡量的话，还是不够的。这种方法的实现代码如下：
public static int findSec(int[] a, int size)
int smallest = 0, second = 1;
for(int i = 1; i & i++)
if(a[i] & a[smallest])
smallest =
swap(a, 0, smallest);
for(int j = 2; j & j++)
if(a[j] & a[second])
return a[second];
public static void swap(int[] a, int i, int j)
int temp = a[i];
a[i] = a[j];
前面的办法是用了两个循环来遍历数组，我们也可以通过一次遍历来实现：
public static int findSecond(int[] a, int size)
int first = 0, second = 0;
if(size & 1)
if(a[0] & a[1])
second = 1;
first = 1;
for(int i = 2; i & i++)
if(a[i] & a[second])
if(a[i] & a[first])
return a[second];
虽然我们能实现达到O(n) 这个量级的方法，但是和前面的要求来说，还是没达到。很显然，第一种办法没法解决。
从堆排序里借鉴的思路
我们前面如果看过堆排序就知道它是一个数组，但是用一种完全二叉树的角度来操作它。比如说我们有一个数组[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]。那么，按照堆排序的思路，它对应的二叉树关系如下图：
这部分的特性对于我们构造调整的结构有什么帮助呢？毕竟这里是在一个已经有的数组中间来构造。但是这里有一个比较有意思的性质，对于我们后面的分析有帮助。假设有一棵完全的二叉树，它的叶结点层也是完全覆盖的，那么这一层的叶结点数目必然为2**k(2的k次方)。从叶结点往上的结点每次都为它的一半，直到根结点。那么，从根结点到叶结点上面一层的所有结点数目正好构成一个等比数列，他们的总数为2**k - 1。也就是说比叶结点数目小1。这给了我们一个提示。就是假设我们有一组元素作为叶结点，然后在它的基础上来构造完全二叉树的上层部分，比如说构造成一个最小堆，那么这部分的花费如果有办法控制的话，有希望实现通过n-1次的比较得到一个这样的最小堆。那么我们看如下的一种构造树的方式：
在这里，假设我们有数组[1, 2, 3, 4] 作为叶结点一层。然后每次两个两个的比较，将较小的那个取出来作为上面一层的结点。那么，在一个理想的情况下，我们假设叶结点总共有2**k个。这次比较生成它上一层的叶结点需要的比较次数为2**(k-1)，也就是说为叶结点数字的一半。再往上一层构造的比较则在原来的基础上再减半。和前面的比较类似，前面所有的比较次数正好构造成一个等比数列，从1到2**(k-1)，那么他们的和就刚好为2**k - 1。经过这一番推导，我们发现通过这么构造一番的方式是可以实现在n - 1次的比较来构造出一个最小堆的。而这个最小堆的构造方式和堆排序的情况不一样。更确切的来说，这个堆有一个明确的说法。它就是胜者树。
后面我们会详细分析胜者树。那么好吧，按照我们原来的要求，是要求实现最后得到第二小的元素，而且比较次数为n + lgn - 2。我们这里只是通过n - 1次比较得到了最小的元素。怎么来找到这个第二小的元素呢？这里又利用到了胜者树一个有意思的地方。我们看前面的图。最终站在顶上的元素是最小的元素。他们所有的比较过程相当于是一个竞赛的淘汰过程。所有参加竞赛的队伍捉对厮杀，然后淘汰到只剩下最后一个。该到哪里找这个第二的呢？这个和具体的比赛不一样。具体的比赛肯定是决赛里头赢的那个第一，输的那个第二。这里头就好像所有pk的怪物都给设定了武力值，武力高的那个赢武力低的那个。可是如果一开始那个武力第二的就和第一的分到一起呢？那么这个老二就很悲催的第一轮被灭了。既然是老二嘛，肯定火力还是比较威猛，也可能一开始没碰到呢？那么他们也可能在中间的某一个阶段碰到，或者在最后的决赛阶段给碰上。总之，最后的冠军已经定下来的情况下，它必然要和这么个老大碰面的。换一个角度来说，我们可以说，它必然会和这么个老大会一面，成为老大夺冠路上的一个冤魂。这样，如果我们要找这个第二小的元素，只要找这个最小元素它曾经比较过的对象就知道了。而我们得到的胜者树可是一路记录了最小元素从小组赛一直pk到决赛的记录的。我们从前面的图中可以看到，只要顺着根结点向下，只要沿着和根结点值一样的结点遍历，那么对应的另外一个结点就是和它pk过的对手。而那个第二小的元素就在它所有pk过的对手里面。
我们看到，我们构造的树是一棵完全二叉树，那么树的高度为lgn。从根结点开始向下走到叶结点进行比较，实际的比较次数为lgn - 1。到这里，我们的思路就完全理清楚了。原来，找这么个老二就是这么一个过程：1. 构造一棵胜者树，这样就可以找到最小的元素。 2. 从根结点开始向下比较每个和它值不同的子结点，然后找到第二小的元素。他们总共的比较次数为n + lgn - 2。
前面是通过一个简单的讨论引出了胜者树。我们来看一个更一般化的胜者树的样子：
胜者树一个更正式的定义是通过锦标赛思想来建立的树，它的每个非终端结点存储的是左右子结点中的优胜者。胜者树实质上是对n个记录的关键字进行两两比较，得到个优胜者，作为第一步比较的结果保留下来。然后这个较小(大)者之间再进行两两比较，…，如此重复，直到选择出最小关键字的记录为止。现在，我们再来看看具体胜者树的构造。
我们前面构思的一个思路是一种比较理想的状态，要求我们的叶结点个数也就是元素的个数为2**k，实际中元素的个数很可能不是正好这么多。那么，按照我们前面堆排序的构造和分析，我们必须要构造这么一个完全的二叉树。我们可以采用两种方式，一种就是将原来的元素补齐，补到刚好大于它数字的2**k个。然后再来构造。还有一种就是我不需要叶结点有2**k个，只要保证从叶结点往上的层正好符合2**k个的标准也可以。就像堆排序构造的堆一样，叶结点不一定是满的，但是上面的结点肯定都是满的。相对来说，第二种方式需要用到的额外空间少一点。我们就以第二种方法为例来讨论。
假定有n个元素，我们总共这棵树需要多少个结点呢？从前面的分析可以得到，需要的元素数目为2**k - 1 + n个。其中2**k为假设叶结点是满的，它所有叶结点的数目。为什么是这么多个呢？我们这里就不再详细推导，只要记住一点，对于一个叶结点是满的二叉树，假设叶结点数目为2**k个，那么它上面其他所有结点的总和为2**k -1，也就是说比满的叶结点数目少一个。
还有一个问题就是，我们是从叶结点向根结点来推导，这n个元素应该放在这个新数组的最后。这部分初始化的代码可以实现如下：
public void buildTree(int[] t)
for(length = 2; length & t. length *= 2);
treeLength = length - 1 + t.
a = new int[treeLength];
for(int i = 0; i & t. i++)
a[length - 1 + i] = t[i];
for(int j = 0; j & length -1; j++)
a[j] = Integer.MAX_VALUE;
build(length - 1, treeLength - 1);
因为这里要比较数值的大小，我们从前面的图里可以看到，有一些上层空缺的位置需要补对应的数值来满足整个满二叉树的结构又不能破坏胜者树的结果，所以我们首先将非n个元素之前的结点值都置成Integer.MAX_VALUE。这里的build方法则是构造的详细步骤，其代码实现如下：
public void build(int start, int end)
while(start != end)
for(int k = k &= k += 2)
if(k + 1 &= end)
a[parent(k)] = a[k] & a[k + 1] ? a[k + 1] : a[k];
a[parent(k)] = a[k];
start = parent(start);
end = parent(end);
public int parent(int i)
if(i % 2 == 0)
return i / 2 - 1;
return i / 2;
在build方法里，每次我们取这一层结点的最左边一个结点和最右边的结点，在遍历的过程中两两比较，将较小的那个设为相邻两个结点的父结点。一直遍历到根结点。
查找的基本过程如下：1. 从根结点开始，看它的左右子结点，如果一个结点和根结点值相同，则取另外一个结点的值作为第二小结点的比较值。2. 进入和根结点值相同的这个子结点，重复步骤1。这个整体过程虽然表述起来比较简单，其实现还是有不少诡异的地方：
public int findSecondMin()
int secondMin = Integer.MAX_VALUE;
int i = 0;
while(left(i) & treeLength || right(i) & treeLength)
if(left(i) & treeLength && a[left(i)] == a[0])
if(right(i) & treeLength && a[right(i)] & secondMin)
secondMin = a[right(i)];
i = left(i);
else if(right(i) & treeLength && a[right(i)] == a[0])
if(left(i) & treeLength && a[left(i)] & secondMin)
secondMin = a[left(i)];
i = right(i);
return secondM
public int left(int i)
return 2 * i + 1;
public int right(int i)
return 2 * i + 2;
这部分的代码就不再详细解释了。有了前面的分析应该也很容易理解。
这一部分是后面新增加的内容。我们在某些情况下，纯粹出于对胜者树的性质的一个维护。如果我们修改了叶结点的一个值，就有可能引起一个连锁的变化。我们看如下的一个示例：
这是按照我们前面的讨论构造的一棵胜者树。如果我们将叶结点1的值修改为4，那么，为了保证树的性质，我们需要做一些如下的修改：
这个过程在于，在原来结点被修改的地方，我们需要重新进行比较和调整，一直向上回溯到根结点。每次需要和它的兄弟结点进行比较。
具体实现的代码如下：
public void adjust(int i, int val)
while(parent(i) &= 0)
if(i % 2 == 0 && i - 1 &= 0)
a[parent(i)] = a[i] & a[i - 1] ? a[i - 1] : a[i];
else if(i % 2 == 1 && i + 1 &= treeLength)
a[parent(i)] = a[i] & a[i + 1] ? a[i + 1] : a[i];
i = parent(i);
这里有一个判断i % 2的地方，是用于判断当前结点的下标值是否为奇数或者偶数。因为胜者树本身的满二叉树属性。所有在左子结点的元素下标值为奇数，右结点的元素下标值为偶数。
这里是根据一个求第二小的数进行的推导。为了找到一个可以更加优化的思路居然要折腾这么多。可见，这些问题背后的思想还是很丰富的。除了胜者树，其实还有类似的数据结构败者树。他们的思想也很类似。在一些更通用的问题比如求最小的若干个数时，还有一些其他的方法和思路，不过和堆也有很强的联系。胜者树，败者树他们和堆排序，求最小（大）的k个元素的问题以及多路归并排序等外排序的算法也有很强的关系。在后续的一些文章中也会针对这几个点八卦八卦。
(922 Bytes)
下载次数: 2
浏览: 1091103 次
来自: 北京
inventory.sort(Comparator.compa ...
&div class=&quote_title ...
讲的很详细，感谢
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix',第二小问,求详解,第一个详解一定给采纳
,第二小问,求详解,第一个详解一定给采纳&
(1)要使函数y=√(mx^2-6mx+m+8)的定义域为R只要⊿=36m^2-4m(m+8)0
我有更好的回答：
剩余:2000字
与《,第二小问,求详解,第一个详解一定给采纳》相关的作业问题
看不清图啊! 再问： 再问： 那解这题
分类讨论,以X=1为分界点打开绝对值Y=（1-a）x+a 0
找到了原题,以下为答案“：(1)设：甲、乙两个工程队单独完成该工程各需x天、y天,则由题意得：24/x+24/y=118/x+18/y+10/x=1,解得：x=40,y=60经检验x=40,y=60均是方程的根.（2）已知甲工程队每天的施工费用为0.6万元,乙工程队每天的施工费用为0.35万元,根据题意,要使工程在规定
∵Rt△A‘AG≌Rt△ABE∴∠AA'G=∠BAE,∵∠AA'G+∠A'GA=90°,∴∠BAE+∠A'GA=90°,∴A'G⊥AE∵D'F//A'G∴D'F⊥AE,∵D’F⊥AD,AD∩AE=A,∴D‘F⊥面ADE,∵D’F 在面A‘DF内,∴面ADE⊥面A'FD.
& 再问： 3Q
& 再问： 必采纳再问： 怎么我的问题你还没回答我
压强小（因为,流速大,压强小） 再问： &再问： 21.题第2问 再答： 阻力是多少？ 再答： 如果阻力是。。再问： 2×10的3次方 再答： &再问： 对吗？ 再答： 望采纳再问： 你确定对吗 再答： 确定再问： 电能的单位是 再答： 电功:J再问： 电能的单位呢 再答： 电能？再问： 恩 再答：
∵DB'∥AE∴∠ADB'=∠EAD=90°∴AD=AB'/2∴∠DB'A=30° ∠DAB'=60°∴∠α+∠CDA=∠DAB'+∠CDA=90°∴∠α=∠DAB'=60°
1,(根号a)^2=0,否则无意义.且a
第二问：∵α是锐角,又cosα＝3/5,∴sinα＝4/5.∴f（α）＝［1＋√2cos（2α－π/4）］/sin（α＋π/2）＝［1＋√2cos2αcos（π/4）＋√2sin2αsin（π/4）］/cosα＝（1＋cos2α＋sin2α）/cosα＝［2（cosα）^2＋2sinαcosα］/cosα＝2（cosα
第一个换成二元一次方程,c=cosx,y=2xx＋2x,x属于-1到1,所以,可以直接求,第二个同时提一个2√3,可以直接化简.
用左手左手定则判断可知电子是向上运动的,正电荷向下运动所以下面的电势高
全部吗? 再问： ??????????再问： ?????????再问： ????????????再问： ???????????????? 再答： ????????к?????????????????再问： ???再问： ??????????????? 再答： ??????再问： ???? ???????再问： ????
m=4.4g 观察1和2组实验数据可以发现,盐酸过量,矿石不足量,且每5克矿石反应完全可放出1.76克二氧化碳,第3组实验说明当加入15克矿石时,盐酸已经不足(比2多5克矿石只多出0.88克二氧化碳),矿石为反应完,故第4组实验当把矿石增加到20克时,生成的二氧化碳的量和第3组一样多
A1B与AB1垂直（正方形对角线）设A1B,AB1交与O点,因为三角形A1BD等腰,所以DO与A1B垂直DO,A1B在面A1BD上,且DO,A1B有交点O所以得证AB1与面A1BD垂直 再问： 正三棱柱侧面是正方形么再问： 为什么AA1B1B是正方形 再答： 因为第一行“正三棱柱所有棱长都为2”，所以侧面自然是正方形啦
x→∞时,[(1+2x)^10*(1+3x)^20]/[(1+6x^2)^15]→[(1/x+2)^10*(1/x+3)^20]/[(1/x^2+6)^15→（2^10*3^20）/6^15=3^5/2^5=243/32 再问： лл??
AP可求=2倍根号5,∠APB一定,过P点作x轴垂线PQ,点B在射线PQ上不于P重合（m＜3）通过画出图即可看出只能三种情况AP=PB AP=AB AB=PB 构造直角三角形勾股定理求出m
再答： 能看懂吗？ 再答： 看不懂可以再问我再问： 嗯懂了，谢谢刚开始学不太熟练>_扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
高中三角函数题第二小问有我的过程与标准答案我哪里错了?已知ab均为锐角，sina=3/5，tan（a-b）=-1/3，求cosb的值我是用cosb=cos（b-a+a）做的求出来与答案不同。答案是用cosb=cos【a-（a-b）做的
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
我猜你错在这里tan(a-b）=-1/3,则tan(b-a)=1/3,故b-a是锐角,sin(b-a)与cos(b-a）均大于零.
为您推荐：
其他类似问题
扫描下载二维码第二小问求解答&
第二小问求解答&
分子,分子,原子,原子,原子,原子,分子,分子.
我有更好的回答：
剩余:2000字
与《第二小问求解答&》相关的作业问题
不是都做了吗
解题思路： 关于欧姆定律计算，详细答案请见解析附件。。 解题过程：
解题思路： 数形结合法求解距离的问题很适合，注意这种数学思想。解题过程：
1-4 AADC第二题可能选C
1 B 第二张最后一行2 B 第三张最后一行, a return ticket 一张来回车票 ,有两次3 C 4 C
因为15千米以后收费标准不再变化,且由第一小问可知乘坐15千米时交费为28元,所以乘客交了95.2元,则出租车行驶了：15+（95.2-28）/2.4=43千米.另由题意不足1千米时按四舍五入计算,可知出租车路程在42.5千米和43.4千米之间时费用均为95.2元,因此出租车最多行驶为43.4千米.
(1)因为∠ACB是直角,所以BC⊥AC,&&& 又因为SA⊥平面ABC,所以SA⊥BC,&&& 而SA∩AC=A,所以BC⊥平面SAC,而SC∈平面SAC,所以BC⊥SC.&（2）做CD⊥AB,又因为SA⊥平面ABC,所以SA⊥CD.所以CD⊥平面
再答： 错了，应该是大于等于号
去掉“的春天”
（2）首先求出两条直线的焦点为（1,2）,设所求的直线方程为y-2=k(x-1),显然k≠0；当x=0时,y=2-k,当y=0时,x=1-2/k；要使得直线在x轴和y轴上截距相等,则2-k=1-2/k;解得k=2或-1,所以方程为y=2x或者y=-x+3
再问： 答案是1到5→_→肯定答案错了吗 再答： 嗯再问： 噢，谢谢
& 再答： &再问： 第2个式子应该是二分之一Tn吧 再答： 1-2应该是-Tn吧 看错了不好意思，第二个对的公比就是2再问： 哦
a=bcosC+csinB结合正弦定理,得&&sinA=sinBcosC+sinCsinB∵A+B+C=π∴sinA=sin（B+C）=sinBcosC+cosBsinC∴sinB=cosB∵0＜B＜π∴B=π/4&
小弟你真是人才.每个学校的期中考试试卷都不一样,你没告诉我们题目你没说是哪个学校的考试,叫大家如何帮你?补充：能否将题目发出来!a表示脚印长度,b表示身高关系为a＝7a－3.07 a b的关系式出错了吧?分别将身高代入关系式得：7a-3.07=1.87 和 7a-3.07=1.75分别解之得 a=0.7057 和a=0
这是要分情况讨论的,第一种情况:当o°
& 再问： 最后一问怎么写第二小问谢谢&&
第二小问谢谢&&
再问： 第二小问呢 再答：
我有更好的回答：
剩余:2000字
与《第二小问谢谢&&》相关的作业问题
利用第一问的结论.a1+1=2第一问求出了an+1的公比是2所以an+1=2^nan=2^n-1若仍有疑问,欢迎追问! 再问： 不懂 再答： 哪一步不懂？说清楚我为你继续解答~再问： 就是第二小问再问： 你用最详细的语言或式子告诉我 再答： 先求首项，a1+1=2,这步不会有什么问题吧。 然后第一问不是求了 a(n+1
等下, 再问： 喔喔 再答： 再答： 再问： 在拍清楚点可以吗 再答： 好的 再答： 再答： 这下清楚点，我手机像素不行，能看见就行了 再答： 能看见吗再问： 看的见再问： 我先搞搞懂 再答： 再答： 再答： 这下应该好点，刚才那个是草稿纸，太薄太差了再问： 为什么是小于等于1啊 再答： 看懂后，要及时采纳，给好评，我
解题思路： 平抛水平方向为匀速，说明时间间隔都相等，竖直方向为自由落体运动，故连续相等时间竖直位移变化均相等且等于gT2.解题过程： 最终答案：
解题思路： 根据三角形面积公式求解解题过程： 请看附件最终答案：略
解题思路： 根据线线平行得到线面平行,线面平行又进一步得到线线平行,再用三角形中的相似比计算解题过程： 请看附件最终答案：略
解题思路： 立体几何解题过程： 其中GF=na是错误的，应该是GF=(1-n)a 此时S=1/2(nb)(1-n)a=(-n2+n)/2. ab 所以当n=1/2时，S取最大值1/8 .ab最终答案：略
角bda为rt角 再答： 求采纳啊
再答： 不用谢，各取所得
解题思路： 1）把点E的坐标代入直线解析式，计算即可求出k值； （2）设点P的横坐标为x，根据直线解析式表示出点P，根据抛物线解析式表示出点B，根据两直线平行，内错角相等可得∠BDP=∠POC，然后根据∠BDP的正切值求出BP与BD的比值，根据点B的坐标求出∠BOC的正切值，再分①当∠BDP=∠BOC时，两三角形相似，
导数学过没?求导简单 再问： 老师让用作差法 再答： 上高几了？再问： 一 再答： 我解看看 再答： 再问： 好不清楚呀，可不可以清楚些，谢谢 再答： 再答： 再问： 好感谢的宁 再答： 给个满意答案吧再问： 会的会的再问： 话说姐姐高几 再答： 高三再问： 那你不好好复习还玩手机再问： 太给力了，你的回答已经完美的解
再问： 可以再问你一道题吗再问： 再问： 第二十五题再问： 谢谢 真的很着急
a=bcosC+csinB结合正弦定理,得&&sinA=sinBcosC+sinCsinB∵A+B+C=π∴sinA=sin（B+C）=sinBcosC+cosBsinC∴sinB=cosB∵0＜B＜π∴B=π/4&
原式=(m²+3)/(m+1)=(m²-1+4)/(m+1)=(m+1)(m-1)/(m+1)+4/(m+1)=(m-1)+4/(m+1)
第一题由题知 AB//CC' &AC//CC'所以四边形ABC'C为平行四边形所以CC'=AB=a由1知 四边形ABC'C为平行四边形所以AC=BC'在三角形BDC'中 因为三角形两边之和大于第三边所以BC'+BD=AC+BD&DC&#39
再问： 谢谢啦！ 再答： 我其实怕你看不清，字草再问： 弱弱的说一句 其实有点看不清再问： 不过仔细看还是能看懂啦！
再问： 再答： 这个方法就剥离参赛，或者参赛分离，就是求t右边的最大值.1+15=15?你小学谁教你的？再问： 看错了…… 再答： t右边是一个一元二次函数，求它的最大值，这总能理解吧。再问： 再答： 这个是一样的，但是这是个关于m的一元二次函数，求这个函数在给定的m的范围内，求它的最大值。再问： 这个我知道的，我问的
你做对了 再问： 老兄，我问得是第2小问求回复
考虑金属盘内电阻为r,E/(r+R)=I1,E/(r+R/2)=I2,两式子把r约掉,得到E(1/I1-1/I2)=R/2圆盘转动的情况就和一根长度为d/2的金属绕端点转动情况一样,根据E=BLV,可以知道,L=d/2速度为改金属棒中点的线速度V=d/4*2pai*N,所以E=Bd*d*3.14*n/4把改式子和上面的
解题思路： （1）木棍滑动的过程中，点P到点O的距离不会变化．根据在直角三角形中，斜边上的中线等于斜边的一半即可判断；（2）当△AOB的斜边上的高h等于中线OP时，△AOB的面积最大，就可以求出． 解题过程：}