- 有一个小白程序员，写了一个只能对5个数字进行排序的函数。现在有25个不重复的数字，请问小白同学最少调几次该函数，可以找出其中最大的三个数？
- 25个数 分成 5 组 A/B/C/D/E，分别排序，5 次。
- 每组选出其中最大的数，排序，1次，假设最大的三个数为
A[0]>B[0]>E[0]
得到的信息：
- A[0]已经确定是最大值了
- C[0]/D[0] < A[0]/B[0]/C[0] ，故最大的三个数一定不存在与 C/D中
分析：最大的三个数分布可能的情况有三种
- 全在 A中
- A中一个，B中两个
- A、B、E 分组中各一个
现在要获取第二、三大值
比较 A[1]、A[2]、B[0]、B[1]、E[0]，其中选出最大的两个数，即分别是第二、三大数
故最少需要比较 7 次
-
在一个axb的整数矩阵中，寻找最长的严格递减数字序列。数列可以沿着横或竖的方向，但不能重叠，该问题的最优复杂度是____。举例来说，以下是一个3x5的矩阵，其结果如下：
image.png
O(a*b)
