同时找最小与最大

Min & Max

专题: Strategy / 策略
难度: L4
来源: Brainstellar

题目详情

给定一个长度为 $n$ 的数组。

找最小值需要 $n-1$ 次比较。
找最大值需要 $n-1$ 次比较。

若要同时找出最小值与最大值，能否少于 $2n-2$ 次比较？

提示：把元素成对比较。

Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons?

Hint

the answer is ~1.5n calculations. It uses a trick. When you compare two elements, one comparison is sufficient to find both min & max of those two elements.

解析

可以，约 $\frac{3n}{2}$ 次。

做法：

把 $n$ 个数两两配对，先在每对里比较一次，得到每对的较小值与较大值（耗时 $n/2$ ）。
在所有“较大值”中找最大（耗时 $n/2-1$ ）。
在所有“较小值”中找最小（耗时 $n/2-1$ ）。

总比较次数约为 $\frac{3n}{2}-2$ 。

Original Explanation

Solution

Solution requires approximately 1.5n comparisons instead of 2n comparisons.

Break n numbers into pairs of 2. So, that is n/2 pairs. Find maximum and minimum in each pair. Cost = n/2. Now given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2

So, overall cost 3n/2 comparisons.