问题描述:寻找数组中的最大值与最小值。
分析:这个问题实际中用的非常多,需要我们好好研究下。我在之前的博客中曾提到过一个线性时间选择算法用来求解TopK问题,同样的这个也可以使用那个算法,实际就是TOP1和TopN,但是由于问题的特殊性,但由于那个算法编程比较复杂,
我们可以采用更加简单的方法。这里我提供几种解法供大家参考。
解法一:线性扫描法。设置两个变量max和min用来保存最大值和最小值,开始时将第一个元素赋值給max和min,然后依次和后面的进行比较即可。这应该是最简单的方法了,大家应该都用的这种方法最多,但是这种方法,当数组很大的时候比较次数过多,
需要比较2n次。好处是查询后原数组位置不变。
解法二:分组法。我们可以将这个数组每两个分为一组,为了方便起见,把相邻的两个分为一组,然后针对每组进行比较,大数放在偶数下标处,小数放在奇数下标处,这需要比较n/2次,然后再设两个标志量max和min,对于每组在进行比较,这样需要比较
2*(n/2)次,所以该方法一共需要比较1.5n次。尤其在数据量很大的时候,该方法减少的比较次数越多。但是该方法破坏了原来数据的顺序。
解法三:在解法二的基础上进行改进,设置两个标志量max和min,针对每一组比较完后,直接把对应的数放到min和max中,这样就不需要交换次序了。整个的比较次数也为1.5n次。
总结:具体使用哪种方法,应该根据具体的环境去选择,各有利弊。