如何寻找数组中的最大值和最小值

以下五种解法可以寻找到数组中的最大值和最小值;

1)问题分解法。

    把本题看做两个独立的问题,而非一个问题,所以,每次分别找出最小值和最大值即可,此时,一共需要遍历两次数组,比较次数为2N次;(N表示数组的长度)

 2)取单元素法。

    维持两个变量min和max,min标记为最小值,max标记为最大值,每次取出一个元素,先与已找到的最小值比较,再与已找到的最大值比较,此种方法只需要遍历一次数组即可;

3)取双元素法。

    维持两个变量min和max,min标记为最小值,max标记为最大值,每次比较相邻的两个数,较大者与max比较,较小者与min比较,通过比较找出最大值和最小值。此种方法的比较次数为1.5N次。

  示例代码如下:【以下有BUG,自己找《如何寻找数组中的最大值和最小值》

<pre name="code" class="java" style="background-color: rgb(255, 255, 255);"><span style="font-size:18px;">public class MaxMin {
	static int Min;
	static int Max;
	public static void GetMaxAndMin(int  arr[]){
		Max=arr[0];
		Min=arr[0];
		int len=arr.length;
		for</span><span style="font-size:18px; font-family: Arial, Helvetica, sans-serif;">(int i = 1; i < len-1; i+=2) {</span>

<pre name="code" class="java"><span style="font-size:18px;background-color: rgb(255, 255, 255);">			if(i+1>len){
				if(arr[i]>Max)
					Max=arr[i];
				if(arr[i]<Min)
					Min=arr[i];
			}
			if(arr[i]>arr[i+1]){
				if(arr[i]>Max)
					Max=arr[i];
				if(arr[i+1]<Min)
					Min=arr[i+1];
			}
			if(arr[i+1]<arr[i]){
				if(arr[i+1]>Max)
					Max=arr[i+1];
				if(arr[i]<Min)
					Min=arr[i];
			}			
		}
	}
	public static void main(String[] args) {
		int array[]={7,12,4,55,22,66,32,101,32};
		GetMaxAndMin(array);
		System.out.println("max="+Max);
		System.out.println("min="+Min);
	}
}</span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">
</span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">输出:max=101
      min=4</span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">
</span>
<span style="font-size:18px;color:#3366ff;"><strong style="background-color: rgb(255, 255, 255);">4)数组元素移动位法</strong></span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">   将数组中相邻两个数分在一起,每次比较相邻的两个数,将较大的数交换至左边,较小值放在右边,对大者组扫描一次找出最大值,对小组遍历一次找出最小值,此种方法比较次数为1.5N—2N之间,但需要改变数组结构;</span>
<span style="font-size:18px;color:#3333ff;background-color: rgb(255, 255, 255);"><strong>5)分治法</strong></span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">将数组划分为两半,分别找出两边的最小值最大值,则最小值是两小之小者,最大者是两大之大者,比较次数为1.5N次。</span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">
</span>
<span style="font-size:18px;background-color: rgb(255, 255, 255);">
</span>




   

    原文作者:JohnLee_chun
    原文地址: https://blog.csdn.net/JohnLee_chun/article/details/52541860
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞