关于在一个无序数组中的数求最大值和最小值的最小比较次数

时间:2022-02-09 15:14:25

在一个又N个数的无序数组中,最少需要比较多少次可以求出这个数组的最大值和最小值?

此题在《编程之美》上有,并且LZ最近在面百度的时候也被问到了类似的题目,微软面试好像也考到了这题。

那么我们来分析,如果实在一个没有重复元素出现的数组中,我们发现一般情况下,最大的和最小的一般不是同一个,所以有好几种方法来求。

第一种:整个数组扫两遍,那么时间复杂度为O(2*N)。肯定不行。

第二种:用分而治之的方法,先让相邻的两个数进行比较,并将大的数放在偶数位置上,将小的数放在奇数位置上,那么就需要N/2次,然后再从奇偶位置上求出最大最小值,这样就还需要比较N/2,所以我们可以发现一共需要1.5N次比较。

第三种,也是用分而治之的思想,但是比较次数并没有减少,先将所有数分成两部分,分别对前一部分和后一部分分别求最大、最小值,最后再做一次比较。但是这样的比较次数并不会少,也是N/2次。

这题可以引申为另一种类型,赛马问题。

首先有25匹马,但是一共只有5条跑道,也就是每次只能有5匹马同时进行赛马比赛,那么最少需要比赛几次才能比出所有25匹马中的最快的3匹马?

分析:首先我们将所有25匹马分成5批次,每一个批次都有5匹马,那么这样就需要比5次,可以决出每一组中的最快的那一匹马,然后再对5个组中的第一名再进行一次赛马比赛,也就是再比一次,那么可以决出前三名来,那么这次比赛的后两名肯定没戏了,连同这两匹马所在那两组里的所有马都是没有希望了,因为这两匹马已经是这两组里跑得最快的了,所以现在我们只需要考虑前三名的马匹即可。那么我们现在可以确定第一名一定是所有马中跑得最快的那一匹马,但是题目需要求前三名,所以我们还需要比。那么我们接下来需要拿第一名所在那一组中的第二名和第三名,然后是第二名以及它所在的那组的第二名,第三名进行加赛一场,正好是5匹马,也就是需要7场,那么这样比下来是一定可以确定前三名来的。这道题主要考的是逻辑。