By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

对于一个由N个整数组成的数组，需要比较多少次才能把最大和最小的数找出来呢？

解析

普通的遍历是需要O(2n)时间，那有没有其他更好的办法呢？
其实可以使用分而治之的思想，将N分为两段 分别取到每一段中的最大和最小值 ，然后最大与最大比即可 最小与最小比即可，这样就可以避免最小与最大的比较

比如：
1,2,3,4
正常对比的话得到min=1,max=4需要6次
那如果先求的min1=1,max1=2,min2=3,max2=4（需要2次比较）
然后min1<min2 得到min=1,max1<max2可得max=4 （又是需要2次）
所以这种方法只需要4次

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private static int compareCount=0;
/**
 * 分而治之的思想，将N分为两段  分别取到每一段中的最大和最小值  ，然后最大与最大比即可 最小与最小比即可，这样就可以避免最小与最大的比较
 * @param a
 */
public static void maxMinInArray(int[] a,int left,int right,Data data)
{
	//当只有两个以及两个以内时才进行比较
	if(right-left<=1)//难道这个索引位置的比较不算？？？
	{
		compareCount++;
		if(a[right]>a[left])
		{
			data.min=a[left];
			data.max=a[right];
		}else{
			data.min=a[right];
			data.max=a[left];
		}
		return ;
	}
	
	Data dLeft=new Data();
	Data dRight=new Data();
	int mid=left+(right-left)/2;
	maxMinInArray(a,left,mid,dLeft);//递归左边
	maxMinInArray(a,mid+1,right,dRight);//递归右边
	
	compareCount++;
	data.min=Math.min(dLeft.min, dRight.min);

	compareCount++;
	data.max=Math.min(dRight.max, dLeft.max);		
}

static class Data{
	public int min;
	public int max;
}

这种方式最终的复杂度是O(1.5n)
测试代码

1
2
3
4
5
6
7
8
public static void main(String[] args)
{
	int[] a = {3, 2, 56, 109, 10, 95, 1, 230, -1000}; 
	Data data=new Data();
	maxMinInArray(a,0,a.length-1,data);
	System.out.println(String.format("min:%s,max:%s",data.min,data.max));
	System.out.println(String.format("length:%s,compare count:%s",a.length,compareCount));
}

min:-1000,max:3
length:9,compare count:13

参考

July微软面试100题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考