第一种方法是进行两次冒泡排序，第一次找出最大的数，需要比较(N-1)次，第二次找出第二大的数，需要比较(N-2)次，所以这种方法总共需要遍历2遍，比较(2N-3)次。第二种方法是声明两个变量a和b，初始化为前两个数，且a&b.然后依次遍历后面的数，如果大于b则替换b，然后调整a和b值，使a&b成立。然后就这样一直进行下去，直到N个数全部遍历完，则b即为所求。这种方法只遍历一遍，但是空间需要额外的两个，且对于大于b数字还需要与a进行再次的比较。最好情况下，a和b恰好是最大值和次大值，此时需要比较的次数最小，算上a和b的初始比较，总共需要(N-1)次。最坏的情况下，a和b恰好是最小值和次小值，此时比较了b之后还需要比较a，那么就退化成第一种算法了。上述两个算法算是可行的。不过，我觉得第二种算法的随机性太大，有没有改进的可能？还有其他更加高效的算法吗？请教各位算法大神。
该问题被发起重新开启投票
投票剩余时间：
之前被关闭原因：
该问题被发起删除投票
投票剩余时间：
距离悬赏到期还有：
参与关闭投票者：
关闭原因：
该问题已经被锁定
锁定原因：（）
保护原因：避免来自新用户不合宜或无意义的致谢、跟帖答案。
该问题已成功删除，仅对您可见，其他人不能够查看。
我这边有一个方案大家探讨一下，由于产生N个数字中，找到最大数字的比较次数为N-1次，这个是不可优化的，可以认为是找出第二大数字的比较次数的下限；这样先将N个数字两两分组，每组取最大值，这样共有N/2+1个组，这样找到最优点需要N-1次比较，但是会剩下N/2+1个点（每组中的最优点，和最大点所在组的两个点），对剩下的N/2+1个数进行比较，产生次最大点需要比较N/2次比较，故总共大约需要比较的次数为3N/2，我们可以将每组中较大的点存在奇数或者偶数位置，从而使得空间复杂度为O(1)；这样实现找到第二个最大点的比较。进而，不考虑空间复杂度的情形下，我们可以进一步减少比较次数，对这N个数进行二分比较，整个比较过程会构建出一个二分的比较树，假定每个数在每轮比较的点都被记录了下来，这样第一轮找到最大点大约需要N-1次比较，而在找到第二大点时，我们可以把和最大点比较过的点集合起来进行比较，树的高度为lgN，所以第二轮比较点的个数为lgN，这样在不考虑空间复杂度的情形下，比较次数恒定为N+lgN，而空间复杂度考虑可以设想用类似静态链表形式实现。可能空间复杂度可以达到O(N)
在找一组数字取第二大数这个问题中其实就是根据先序比较消除冗余匹配的策略，我这边有一个想法虽然和前述方法相比不是在时空复杂度上不是最优，但是可以提供一种思路，若有更好的方法可以基于此进行优化，方法如下：基本思想是：通过一次匹配，利用第一次遍历比较过程中获取的数据间相对大小信息来消除第二次遍历过程中不必要的比较；具体方案：设定一个rank数组，长度为N，对应N个数，每个值表示数组中现在已知比当前数大的数的个数，初始化为0，表示当前已知的比当前数大的数的个数为0个数，这样，先取第一个数和后面的数进行比较，较小数的rank值增1（表示对应数字），若当前数的rank值大于等于2，表示数组中已经有两个数比当前数大，所以这个数不可能为第二大值，抛弃之；检查下一个数，若下一个数的rank值大于等于2，则不进行比较了，继续拿下一个数字进行比较；如此重复，直到有一个数比较完所有数之后rank值为1；经过我用多个序列进行测算，发现最终的匹配次数和冒泡排序一致，为2N-3次，但是空间复杂度为O(N)，有一些退化，但是希望后来有人对这个想法进行优化
说一个思路。1、每两个元素成组比较，需要n/2次——形成数据对；2、数据对比较，按照较大的那个数比较；3、反复2，直至余下的数据只有1个。（当然，不能丢弃之前的比较结果。）这样，构建出一个二叉树。如果一个数据对，连续比较两次都小，那么这个数据对就可以丢弃了。也就是丢弃上面那个树，三层之外的节点。那么余下就是固定比对次数了。2和3的比较次数，应该是O(n)。
我是新手啦，只是来发表一下意见...可能上面已经说了我说的这个方法...但是我有些术语看不懂...我比较直白的表达一次我的想法...
我是觉得...N个数两两比较...大的提取出来...一直比到得出最大的,需要比较N-1次...然后剩下两个最接近最大数的两个数比较...就得出第二大的...一共比较N次...
譬如...1 5 2 6 3 7 4 85 6 7 86 88然后6和7再比一次(最近跟8比较的两个数)牺牲了O(N)个空间...感觉最后的判断有点难写...要不要剩下最后三四个的时候来个冒泡算了...最多也是N+1次?
上面的错了...算出最大的数之后,还要把所有跟最大的数对比过的数搜集起来...再求一次最大数... - -,那就要3N/2次了...没什么用...
&?php $n = rand(100,200);$number = $n;$array = array();for($i=0;$i&$n;$i++){
$array[$i]['number'] = rand();}/*$array2 = $sort($array2);print_r($array2);echo "&br /&";print_r($array);*/$counts = 0;for($i=0;$i&$n;$i=$i+2){
if($i+1&$n){
if($array[$i]['number'] & $array[$i+1]['number']){
$array[$n]['number'] = $array[$i]['number'];
if(!empty($array[$i]['kill'])){
$array[$n]['kill'] = $array[$i]['kill'];
$array[$n]['kill'][] = $i+1;
$array[$n]['number'] = $array[$i+1]['number'];
if(!empty($array[$i+1]['kill'])){
$array[$n]['kill'] = $array[$i+1]['kill'];
$array[$n]['kill'][] = $i;
$counts++;
$n++;}$k = count($array) - 1;$zuida = $array[$k]['number'];/*echo "&br /&";print_r($array);*/$dierda = '';foreach($array[$k]['kill'] as $numbers){
$dierda = (empty($dierda))?$array[$numbers]['number']:$
$dierda = ($array[$numbers]['number'] & $dierda)?$array[$numbers]['number']:$
$counts++;}$counts = count($array) - $number + (count($array[$k]['kill']) - 1 );echo "N:".$echo "&br /&";echo "count:".$echo "&br /&";/*echo "&br /&";echo $echo "&br /&";echo $*///最后$array里面个数 - $numbers 其实就是 N-1,
$array[$k][kill]里面的个数其实就是 floor(log2(N)) 最后还要减1;
还有人看我这个吗?求顶啊!!!计算次数是 N-1 + log2(N) - 1 呢...就是记录了每个数打败了谁,每个数最多比较floor(log2(N))次...提取出来再求最大值...那就比较次数很少了...就是浪费了很多空间...N-1 + log2(N) - 1啊~~给分啊~~~
我用的是第二种方法。代码如下：
#include&stdio.h&
#include&stdlib.h&
int find(int *a,int n)
int second=*(a+i);
while(i&n)
if(*(a+i)&second)second=*(a+i);
int findsecondmaxvalue(int *a,int n)
int first=*(a+i);
int second=*(a+i);
while(i&n)
if(*(a+i)&first)
first=*(a+i);
else if(*(a+i)==first)
//do nothing
else if(*(a+i)&first&&*(a+i)&second)
second=*(a+i);
//do nothing
//最大值和次大值相等(只可能出现在数组的第一个元素)
if(first==second)
second=find(a,n);
int main()
int a[]={9,5,1,7,4,6,2,3,8};
int n=sizeof(a)/sizeof(a[0]);
int second=findsecondmaxvalue(a,n);
printf("次大值=%d\n",second);
把数列分成两份，分别取最大值，然后再比较两个最大值……可以不？
基数排序，数据规模不大的情况下用全覆盖基数，一遍搞定，空间换时间的经典解决方案。这类问题数据规模是性能的一个重要制约因素，不同规模有不同的解决方案的，不能一概而论，毕竟每种方案的最优覆盖领域是不一样的~~
这不是数据结构堆排序吗？？取出前两个根节点就是了。
我的方法是参考《编程珠玑》第一章解决排序的方法，使用位图排序。前提条件是知道N的集合范围，此方法适合用于有限和稠密集合，遍历[N+1,2N－1]次就出结果，缺点是很占内存空间（N要小于1亿）。
解题步骤：假设N的集合范围[0,5]，N个数为{2,4,5,1}初始一个一维数组｛0，0，0，0，0，0｝。然后遍历N次，每次把数值所对应的数组下标值设置为1，遍历后数组为{0,1,1,0,1,1}.这样就可以从数组末尾倒数第二个开始向前找，只要遇到值为1，就输出数组下标值。
所以最好的结果是在数组N-1个找到，最坏结果是在第一个找到。所以程序查找次数为[N+1,2N－1]。
想了一个方法首先将进行N个数二分，分别在每组中利用冒泡排序选出最大的数，然后比较这两个最大的值，这样比较下来是N-1次，然后选择最大的所在的组，去除这个最大值，剩余的N/2-1个数再冒泡排序一次，得到最大值这个最大值与另外一组的最大值进行比较，如果这个值较大，这个就是第二大的，否则，另外一组的最大值是第二大的。这部分比较的次数是N/2-1次综合起来是比较了3N/2-2次相对两次冒泡排序，次数有所减少。
我觉得应该使用堆排序的方法。使用大顶堆。
我今天在网上闲逛，无聊之中发现一个叫&左耳朵耗子&的人在酷壳上写的一篇博文。地址如下：
所以专门跑来贴链接。希望对你有所帮助。
我觉得可以考虑使用经典快速排序中使用到的parition算法，就是划分法，每次找当前数组中间的数，然后丢弃一半，继续找，直到找到k=1(下标从0算起)，就可找到第2大的那个元素。时间复杂度是o(N)
可使用桶排序的思路。扫一遍数据，并把它们扔到各自的桶中。如果桶是升序的，那最大和第二大的数就在最后那个桶或倒数第二个非空桶中。如果该桶中的数据仍然很多，可再次桶排序，直至求出第二大数，或可以接收其他排序方式为止。
效率的话，决定于如何根据具体的数据来设计&桶&。因为桶排序一般不需要比较，所以只要设计好&桶&，效率就应很高。
桶排序有两个特例，即基数排序和计数排序。
不是您所需，查看更多相关问题与答案
德问是一个专业的编程问答社区，请
后再提交答案
关注该问题的人
共被浏览 (15567) 次一，问题描述
给定一个整数N，求解该整数最少能用多少个Fib数字相加得到
Fib数列，就是如： 1，1，2，3，5，8，13....
Fib数列，满足条件：Fib(n)=Fib(n-1)+Fib(n-2)&& Fib(0)=1&& Fib(1)=1；Fib数字，就是Fib数列中的某个数。
比如70 = 55+13+2，即一共用了3个fib数字得到
二，问题求解
①求出所有小于等于N的Fib数字
//获得小于等于n的所有fib数
private static ArrayList&Integer& getFibs(int n){
ArrayList&Integer& fibs = new ArrayList&Integer&();
int fib1 = 1;
int fib2 = 1;
fibs.add(fib1);
fibs.add(fib2);
while((fibn = fib1 + fib2) &= n)
fibs.add(fibn);
fib1 = fib2;
②其实这个问题，可以转化为一个"完全0-1背包问题"。
所谓完全0-1背包问题是指：每个物品可以重复地选择。而这里，每个Fib数字则可以重复地选择。
如：70=34+34+2，34就选择了两次，fib(i) 最多可选择的次数是：N/fib(i)，也就是说：将某个Fib数字拆分成(复制成)多个相同与原来值相同的Fib数字。这样，就相当于每个数字只能够选一次，即要么选择它、要么不选择它。
这样，就将完全0-1背包问题转化成普通的0-1背包问题。
这样，就可以把上面求得的ArrayList中存在的Fib数字&扩充&成具有重复Fib数字的ArrayList
比如，对于70而言：扩充后的fib数组为：会有70个1，70/2个 2& ......
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
8, 8, 8, 8, 8, 8, 8, 8,
13, 13, 13, 13, 13, 21, 21, 21,
根据普通0-1背包问题，对于这个问题，每次总是优先选择最靠近N的那个fib数字，然后再考虑比N次小的那个fib数字......
也就是说，每次总是尽可能地选择接近N的fib数字
其实，这相当于一个贪心问题.
因为对于贪心而言，是先做选择，这个选择在当时看起来是最优的，然后得到一个子问题。比如：对于70而言，先选择比70小的最靠近70的那个fib数：55
此时，得到的子问题就是 求解 15 （70减去55） 最少能用多少个Fib数字相加得到？
一点关于这个问题的贪心算法正确性的证明。
设 S={f(1)，f(2)，....f(n)}是一组不大于N的fib 数列，且S已经排序，那么f(n)是小于N 且 最接近N的那个fib数。
我们要证明的则是：S的某个最优解中一定包含了f(n)
假设S(i)={f(i1)，f(i2),.....f(ik-1)，f(ik)}是N的一个最优解，并且 S(i)集合中的fib数 已经从小到大排序。也就是说：S(i)是 所有 具有最少个fib数的集合，即，&S(i)=N 且S(i)中包含的元素个数最少。
若 f(ik) = f(n)，因为S(i)是最优解，而f(n)又等于S(i)中最后一个元素，故S的最优解S(i)包含了f(n)，得证。
若f(ik) != f(n)，那么f(n)&f(ik)，因为f(n)是最接近N的fib数，是S集合中的max。此时，我们可以运用&剪枝&思想。把 f(ik)从 S(i)中删除，并将 f(n) 添加到S(i)中。设剪枝后的集合为S&P(i)
如果S(i)中没有重复的元素，删除f(ik) 并添加了 f(n)之后，&S&P(i)&N。那么，为什么使&S&P(i)=N，就需要再从S&P(i)中删除某些元素。
此时，S&P(i) 是一个包含了f(n)且元素个数比 S(i)更少的集合。因此，它是一个更优的解。
比如 70=55+13+2 比 70=34+21+13+2 更优。
如果S(i)中有重复的元素，我们需要证明的是S&P(i)中的元素个数最多 和 S(i)中的元素一样多，但是不会比S(i)更多。
这个证明会用到 Fib数列的性质 ：Fib(n)=Fib(n-1)+Fib(n-2)
先举个例子，70=34+34+2&& 与& 70=55+13+2， 在这里f(n)-f(k)=55-34=21
而，fib(n)=fib(n-1)+fib(n-3)+fib(n-5)+....+fib(k)
（具体的证明不会啊。有大神可指教啊。。。）总之，应该用贪心算法是正确的。
关于证明，还可参考：中的证明。感觉应该很类似。
关于贪心算法正确性的证明，可参考& 中的关于&活动选择问题&的贪心正确性证明分析。
而对于DP，是先寻找子问题的最优解，然后再做选择。
三，参考资料
整个完整代码：
1 import java.util.ArrayL
3 public class Solution {
//获得小于等于n的所有fib数
private static ArrayList&Integer& getFibs(int n){
ArrayList&Integer& fibs = new ArrayList&Integer&();
int fib1 = 1;
int fib2 = 1;
fibs.add(fib1);
fibs.add(fib2);
while((fibn = fib1 + fib2) &= n)
fibs.add(fibn);
fib1 = fib2;
//将之转化成 可重复选择的 0-1 背包问题
private static ArrayList&Integer& augument(ArrayList&Integer& fibs, int n){
ArrayList&Integer& dupfibs = new ArrayList&Integer&();
for (Integer integer : fibs) {
int times = n///每个fib数字最多可选择多少次
for(int i = 1; i &= i++)
dupfibs.add(integer);//"拆分"fib数字
//贪心算法,每次贪心选择最靠近
private static int dp(ArrayList&Integer& dupfibs, int n){
int currentSum = 0;
int count = 0;//需要使用的fib数字 个数
while(currentSum != n){
for(int i = dupfibs.size()-1; i &= 0; i--){
currentSum += dupfibs.get(i);
count++;//表示选择了这个fib数
if(currentSum & n)
currentSum -= dupfibs.get(i);
count--;//选择的fib数相加之后越过了n，因此不能选择它
//功能入口
public static int function(int n){
ArrayList&Integer& fibs = getFibs(n);
fibs = augument(fibs, n);
int result = dp(fibs, n);
public static void main(String[] args) {
int result = function(70);
System.out.println(result);
&此种方法的唯一缺点就是空间复杂度太高了。需要保存大量重复的Fib数字。
阅读(...) 评论()}