求N个数的最大值和最小值，最少的比较次数

Question

答案是3N/2，我没搞懂其中的原理，希望大佬们点醒我一下，谢谢了

Answer 1

liuyubobobo 2017-08-23 02:15:18

这个问题其实还挺有意思的：）

最简单的思路，是从头到尾遍历一遍，对于每一个元素，都和当前找到的最大值和最小值比较一下，看看它是不是新的最大值和最小值。这样做，除了第一个元素，后续每一个元素都需要比较两次，最坏总共需要2(n-1)次比较。

但是，其实我们不需要对于每一个元素，都判断它是不是新的最大值和最小值。因为一个元素不可能同时是最大值，又是最小值。我们可以两个元素两元素来，每两个元素先进行一次比较，其中大的元素才有可能是新的最大值；小的元素才有可能是新的最小值。这样，我们只需要再将大的元素和已经找到的最大值作比较；小的元素和已经找到的最小值作比较就好了。这种情况下，我们每处理两个元素，只需要进行3次比较，总共大致需要(3/2)*N次比较。如果要想获得准确的比较次数，这里需要对N是奇是偶进行分类讨论，有兴趣可以自己试试看：）

这是个很好的问题，有时间我要写一篇详细的文章介绍。感谢你的好问题：）

加油！

• 提问者 Mark1900 #1

  懂了，谢谢老师