同时找出一个数组的最大和最小的数 对于一个由N个整数组成的数组 需要比较多少次才能把最大和最小的数找出来
面试的时候面试官有闻过此题 但是我一直不明白当时问的是什么意思 没有考虑到比较次数 以为时间复杂度为O（N)了还想怎么样，Naive、、、直到在书上看见此题。。。
- 比较次数 最直接的是比较2N次 ，找最大最小数各比较N
- 一般最大数和最小数不会是同一个 可以考虑将数组分成两部分 再从这两部分中找出最大数和最小数将数组按两两划分（a[0][a1]),(a[2][a[2]),,, 比如将两个数中较大的数放在奇数位置 将较小的放在偶数位置 然后遍历奇数位置得到最大值 遍历偶数位置得到最小的数比较次数： 比较两两相邻的数 ，N/2次 遍历奇数位置和偶数位置找到最大和最小值 比较N次 总的比较次数为N/2+N次
- 第二种方法破坏了原数组的顺序 我们可以设置一个MIN和MAX来保存比较结果 按照第二种方法将数组两两分组 比较 较大的数与MAX比较 如果比MAX大 则MAX=较大的数 如果较小的数比MIN小 则MIN=较小的数 到便利完数组后 MAX 和MIN分别保存了数组的最大和最小值 比较次数： 比较两两相邻数 N/2次 与MAX和MIN比较 N次 总的次数仍为 N/2+N 次
- 分治法： 在N个数中 求最大值和最小值 只需要求出前后N/2个数的MIN和MAX 然后取较小的MIN和较大的MAX （比较两次）
假设f(N)表示这个算法对于N个数的比较次数 f(N)=1
f(N)=2*f(n/2)+2
=2*(2*f(n/4)+2)+2
...
=1.5N -2
求N个数值中第二大的数:用分治法 但是对于重复的数 也就是最大值 第二大数 有重复的 分治并不能解决问题 比如 1 ，2,4,4,
但是对于每个元素只出现一次的情况下分治还是可以的
先求出左右边的最大值left1 ,left2 ,right1 ,right2
a.如果left1>right1 那么left1是最大的数 次大的数 应当是left2和right1之间比较产生
b.如果right1>left1 那么right1是最大值 次大的数 应当是right2和left1之间比较产生