编程之美 2.10 扩展问题:求数组中给的第二大数
题目如下:
如果需要找出N个数组中的第二大数,需要比较多少次呢?是否可以使用过类似的分治思想来降低比较的次数呢?
解法一
我们最容易想到的方法就是:我们数组进行排序,取倒数第二个数即为所求。但是比较次数是很高的,不可取。
解法二
用2个中间变量来保存最大值和第二大的值,遍历一次数组即可得到最大值和第二大的值。比较次数为:2*N
实现代码如下:
package com.wrh.firstpro;
import java.util.Arrays;
public class ProgrammingBeautiful_2_2 {
public static void main(String[] args) {
int arr[]={20,1,5,7,4,8,9};
int max;
int secondMax;
max=arr[0];
secOndMax=Integer.MIN_VALUE;
for(int i=0;iif(arr[i]>max){
secOndMax=max;
max=arr[i];
}
else if(arr[i]>secondMax){
secOndMax=arr[i];
}
}
System.out.println("数组"+Arrays.toString(arr)+"第二大的数为:"+secondMax);
}
}
解法三:分治法
我们将数组分成两个子数组,我们可以先分析下最大值和第二大的值可能出现的位置如下
- 最大值和第二大值可能同时出现在一个子数组中
- 最大值和第二大值的值出现在不同的子数组中
因此,我们需要利用四个中间变量分别用来表示两个子数组中的最大值和第二大的值。
实现代码如下:
package com.wrh.firstpro;
import java.util.Arrays;
public class ProgrammingBeautifuldemo_2_2 {
public static void main(String[] args) {
int arr[]={30,40,70,31,9,10,15,-7};
int arr1[]=findMaxAndSecondMax(arr,0,arr.length-1);
System.out.println("数组"+Arrays.toString(arr)+"中的最大的数和第二大的数为:"+Arrays.toString(arr1));
}
private static int[] findMaxAndSecondMax(int[] arr,int left,int right) {
int max,secondMax;
if((right-left)<=1){
if(arr[left]else{
max=arr[left];
secOndMax=arr[right];
}
int temp_arr[]={max,secondMax};
System.out.println(" 每次返回的数组:"+Arrays.toString(temp_arr));
return temp_arr;
}
int middle=left+(right-left)/2;
int temp_left[]=findMaxAndSecondMax(arr,left,middle);
int temp_right[]=findMaxAndSecondMax(arr, middle+1, right);
if(temp_left[0]>temp_right[0]){
max=temp_left[0];
if(temp_right[0]>temp_left[1]){
secOndMax=temp_right[0];
}
else{
secOndMax=temp_left[1];
}
}
else {
max=temp_right[0];
if(temp_left[0]>temp_right[1]){
secOndMax=temp_left[0];
}
else{
secOndMax=temp_right[1];
}
}
int maxSecondMax[]={max,secondMax};
System.out.println("shuzu wuwu"+Arrays.toString(maxSecondMax));
return maxSecondMax;
}
}
上面的递归表达式为f(n)=2*f(n/2)+2,比较次数为1.5*n-2,即时间复杂度为:O(n)
其它解法
也可以按顺序将数组中相邻的两个数分在同一组(这也只是概念上的分组,无需做任何实际操作),然后借助两个中间变量保存max和secondMax,遍历一次数组即可得到我们想要的结果。