正文
查找最大和次大元素（JAVA版）（分治法）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
问题描述：对于给定的含有n个元素的无序序列，求这个序列中最大和次大的两个不同元素。
问题求解分析（分治法）：先给出无序序列数组a[low...high]。第一种情况为当数组中只有一个元素时，此时只存在一个最大值即为本身，次大值为负无穷，在这里我设置为-999999，第二种情况为数组中只有两个元素，此时最大值和次大值很显然将两个元素比较即可。第三种情况为数组中的元素大于两个，此时用分治法，将数组中元素砍为两半，像我们将香肠折半，注意的是此时中间的点归为前半部分，接着我们对前半部分再次进行判断三种情况，再对后半部分做同样的操作，因为我们每次判断返回的都是当前判断的一部分的最大值和次大值，因此折半后两边都有最大值和次大值，再将两边的四个值比较找出最大值和次大值。
代码如下：
import java.util.*;
public class Main {
static int a[];//存放数据的数组
static int inf=-999999;//自定义最小值
public static void main(String args[])
{
a=new int[5];
a[0]=4;a[1]=3;a[2]=5;a[3]=9;a[4]=1;//测试数据，可修改为键盘输入
max m=solve(0,4);//调用solve方法求出最大值和次大值
System.out.println(m.max1+" "+m.max2);//输出
}
static class max//自定义类（存放最大和次大值）
{
int max1;//最大值
int max2;//次大值
max(){};//构造函数
}
static max solve(int low,int high)//low和high为数组中的起始下标和终止下标
{
max mm=new max();//声明，因为每次寻找返回的最大值和次大值都要更新
if(low==high)//如果只有一个元素
{
mm.max1=a[low];//最大值为本身
mm.max2=inf;//次大值为inf
}
else if(low==high-1)//如果只有两个元素
{
mm.max1=Math.max(a[low], a[high]);//最大值为两个元素中的最大值
mm.max2=Math.min(a[low], a[high]);//最小值为两个元素中的最小值
}
else//大于两个元素
{
int mid=(low+high)/2;//设中间值为mid
max m1=solve(low,mid);//m1为前半部分的最大值和次大值（包括a[mid]）
max m2=solve(mid+1,high);//m2为后半部分的最大值和次大值
if(m1.max1>m2.max1)//如果前半部分最大值大于后半部分最大值
{
mm.max1=m1.max1;//更新最大值为前半部分最大值
mm.max2=Math.max(m1.max2,m2.max1);//次大值为前半部分次大值与后半部分最大值的最大值
}
else
{
mm.max1=m2.max1;//更新最大值为后半部分最大值
mm.max2=Math.max(m2.max2, m1.max1);//次大值为后半部分次大值与前半部分最大值的最大值
}
}
return mm;//返回
} }
注意：每次调用solve方法时，都要初始化mm，因为这样才能使low和high更新时，mm中每次存放的为low~high的最大值和次大值；
空吧哇~
