错题整理（422）

表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值，表尾是指除去表头后剩下的元素组成的表（即使只剩一个元素也视为表），可以为空表。

 

有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是：

每个元素要用行号,列号,元素值来表示,在用三元组表示稀疏矩阵,还要三个成员来记住,矩阵的行数列数,总的元素数,所以所需的字节数是10*（1+1+1）*2+3*2=66。

 

在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行（）次比较：

 比如 A B C D E F G H，通过8进4的方式，A与B比较， C与D比较.....然后再4进2，A与C比较（假设A,C比B,D大），E与G比较。再2进1，比如A与E比较（假设A，E比C,G大）选出最大的A，总共7次。

   然后次大的数一定是被最大数PK下去的，所以再选B C E三个比较2次得到次大的数

                                                     A

                             A                                              E

               A                          C                    E                   G    （7次）

       A             B            C           D       E          F      G           H

 

再选 BCE中最大的（2次），共9次，不过可以这个方法比较次数是少一点，但是所需要的空间大，要记下与沿途的最大值比较的数。

分析：这是一个考最优算法的下界问题。

选择问题的复杂度下界，已经有证明，可参考算法导论或屈婉玲的算法设计与分析技术这本书。

对于选择问题，找最大问题的下界是：n-1

找第二大问题的下界是：n+logn-2

 

因此，本题，n=8，代入下界公式：8+3-2 = 9。

 

 

vector erase以后，itor已经指向下一个元素了，不应该执行itor++， 否则会跳过下一个元素http://blog.csdn.net/dgyanyong/article/details/21268469

 

 

一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，这个序列的初始值从1开始，但是1并不在这个数列中。求第1500个值是多少：

2、3、5的最小公倍数是30。[ 1, 30]内符合条件的数有22个。如果能看出[ 31, 60]内也有22个符合条件的数，那问题就容易解决了。也就是说，这些数具有周期性，且周期为30.

       第1500个数是：1500/22=68   1500%68=4。也就是说：第1500个数相当于经过了68个周期，然后再取下一个周期内的第4个数。一个周期内的前4个数：2,3,4,5。
故，结果为68*30=2040+5=2045