题意同题目,一道很简单的面试题,不过最开始我竟然没有想到最优解emmm(太菜了)。
答案在下面,先想想再看答案。
8个元素两两比较,比如ABCDEFGH, A和B比,C和D比,以此类推,得出4个优胜者,4个优胜者继续两两比较,得出2个优胜者,2个优胜者再比较,得出最大值。这波操作比较了7次。然后求第二大,除了被第一大干掉的失败者,其它失败者已经输了,因为赢他们的元素不是最大值,所以他们不可能是第二大,那么第二大只能在被最大值干掉的情况中产生,第一大元素在之前的两两比较中干掉了3个元素,这3个元素相互比较2次,就得出第二大了。总共比较7+2次。