这是一个采访问题:给定整数数组,找到最大值。和分钟。使用最小比较。
显然,我可以在数组上循环两次并~2n在最坏的情况下使用比较,但是我想做得更好。
~2n
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)
这样,您将对2个元素进行3个比较,总计3N/2为N元素的总比较。
3N/2
N