牛客网习题

1. 有一个小白程序员，写了一个只能对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 次

2. 在一个axb的整数矩阵中，寻找最长的严格递减数字序列。数列可以沿着横或竖的方向，但不能重叠，该问题的最优复杂度是____。举例来说，以下是一个3x5的矩阵，其结果如下：

   
   image.png
   

   O(a*b)