如何找到最大。和分钟。在阵列使用最小的比较？ [英] How to find max. and min. in array using minimum comparisons?

问题描述

这是一个面试问题：给出一个整数数组找到最大。和分钟。用最小的比较。

显然，我可以遍历数组两次，在最坏的情况下使用〜2N 的比较，但我想做得更好。

解决方案

  1。选择2元（A，B），对它们进行比较。 （说＆GT; B）
通过比较2.更新分钟（分钟，二）
通过比较3.更新最大值（最大，一）
 

这样你会做3比较了2元，共计 3N / 2 共比较了 N 元素

This is a interview question: given an array of integers find the max. and min. using minimum comparisons.

Obviously, I can loop over the array twice and use ~2n comparisons in the worst case but I would like to do better.

解决方案

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.

这篇关于如何找到最大。和分钟。在阵列使用最小的比较？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！