8个随机整型变量,求最大和第二大元素,需要比较几次?

题意同题目,一道很简单的面试题,不过最开始我竟然没有想到最优解emmm(太菜了)。
答案在下面,先想想再看答案。
















































8个元素两两比较,比如ABCDEFGH, A和B比,C和D比,以此类推,得出4个优胜者,4个优胜者继续两两比较,得出2个优胜者,2个优胜者再比较,得出最大值。这波操作比较了7次。然后求第二大,除了被第一大干掉的失败者,其它失败者已经输了,因为赢他们的元素不是最大值,所以他们不可能是第二大,那么第二大只能在被最大值干掉的情况中产生,第一大元素在之前的两两比较中干掉了3个元素,这3个元素相互比较2次,就得出第二大了。总共比较7+2次。

推一波小姐姐手写的推导2333

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容