最近看到一篇博客登出了一道阿里的笔试题,关于最快的时间复杂度取出一个数组中的最大,以及最小值的问题,所以自己也就思考了下。大部分人的比较次数应该就是2N了。我想的这个算法思想,好像还有好一点,所以就贴出来,供大家看看。如果思路出问题了,烦请各位指出来。
给出示例数组：4 1 5 9 9 7 10 2 (N = 8)
思想大概是这样的：
1 . 比较1 和 N , 2 和 N-1 ...继续下去, 如果左边的比右边的大就互换。局部性上, 就会呈现左边的部分里必定有最小值，而右边的也绝对保存了最大值。
第一轮过后就成了： 2 1 5 9 ~ 9 7 10 4
2 . 在分开的左右部分中各自寻找最小值与最大值
第二轮过后就成了： 2 1 ~ 5 9 ~~4 7 ~ 9 10 (紫色为无需比较的部分)
3 . 这样左边部分又被划分成左边的左边部分， 右边的右边部分
第三轮过后就成了： 1 ~ 2 ~~ 5 9 ~~~ 4 7 ~~ 9 ~ 10
这样三轮过后就找出了最小值与最大值了。
数学分析比较次数(对于单边)：
第1次比较的次数就是N/2^2 （数组比较长度为N/2, 再次对半）
.......
第n次比较的次数就是 N/2^k (N/2^k=1的)
N/2^k = 1 的最后一次比较。所以针对于左半边的次数就是
(N/2^2 + N/2^3 + ....+ N/2^k)
总的比较次数就是： N/2 + 2(N/2^2 +N/2^3 + .... + N/2^k) = 3N/2 - 2
时间复杂度为常数了！(正对于奇数个数组个数,只要在最后将数组的中间位和a[0] 或者 和 a[N-1]比较即可)，
代码我就不写了,大伙有兴趣自己写写吧,不难。
算法流程：
如果是偶数个数的： 直接对半,比较即可,例如： 4 1 2 5 3 6 8 4 => 4 1 2 5 | 3 6 8 4
如果是奇数个数的： 先抛弃中间那个,再比较,例如： 4 1 2 5 3 6 8 4 10 => 4 1 2 5 | 3 | 6 8 4 10 最后再跟3比较下就好。