import java.util.Arrays;
public class MinMaxInArray {
/**
* 编程之美 数组的最大值和最小值 分治法
* 两种形式
*/
public static void main(String[] args) {
int[] t={11,23,34,4,6,7,8,1,2,23};
int[] re=new int[2];
minMax(t,0,t.length-1,re);
System.out.println(Arrays.toString(re));
re=minMax2(t,0,t.length-1);
System.out.println(Arrays.toString(re));
}
//C语言可以传递int& max,int& min.Java不行,用数组代替
public static void minMax(int[] a,int s,int e,int[] result){
if(!isValidParam(a,s,e)){
return;
}
if(s>e){
return;
}
if(s==e){
result[0]=a[s];
result[1]=a[s];
return;
}
int min=0;
int max=0;
if(s+1==e){
if(a[s]<a[e]){
min=a[s];
max=a[e];
}else{
max=a[s];
min=a[e];
}
result[0]=min;
result[1]=max;
return;
}
int[] resultA=new int[2];
int[] resultB=new int[2];
int mid=s+(e-s)/2;
minMax(a,s,mid,resultA);
minMax(a,mid+1,e,resultB);
min=resultA[0]<resultB[0]?resultA[0]:resultB[0];
max=resultA[1]>resultB[1]?resultA[1]:resultB[1];
result[0]=min;
result[1]=max;
}
public static int[] minMax2(int[] a,int s,int e){
if(!isValidParam(a,s,e)){
return new int[0];
}
int min=0;
int max=0;
if(s==e){
min=a[s];
max=a[s];
}else if(s+1==e){
if(a[s]<a[e]){
min=a[s];
max=a[e];
}else{
max=a[s];
min=a[e];
}
}else{
int mid=s+(e-s)/2;
int[] resultA=minMax2(a,s,mid);
int[] resultB=minMax2(a,mid+1,e);
min=resultA[0]<resultB[0]?resultA[0]:resultB[0];
max=resultA[1]>resultB[1]?resultA[1]:resultB[1];
}
return new int[]{min,max};
}
private static boolean isValidParam(int[] a,int s,int e){
if(a==null||a.length==0){
return false;
}
int len=a.length;
if(!(s>=0&&s<len&&e>=0&&e<len)){
return false;
}
return true;
}
}
分享到:
相关推荐
分治法--找最大值与最小值的源代码,很经典,用C++写的。
最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大值的两个大值,4个最小值数组的两个最小值!不知道是不是分治法,...
分治算法实验(用分治法查找数组元素的最大值和最小值).doc
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
分治法求最大值和最小值 实验报告
利用分治法快速而有效的求出任意数组的最大值与最小值。 编码用C++实现
常规的做法是遍历一次,分别求出最大值和最小值,但我这里要说的是分治法,将数组分成左右两部分,先求出左半部份的最大值和最小值,再求出右半部份的最大值和最小值,然后综合起来求总体的最大值及最小值。...
数据结构的分治法求解最大值,数据结构的分治法求解最大值
分治法求最大值的c++的简单实现,代码简单容易理解
设计分治法求一个数组中最大元素的位置,建立该算法的递推式并求解。
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
。。。
。。。
分而治之的思想解决求一个数组的最大子集,有效的降低了时间复杂度,值得学习。
。。。
。。。
分治法解决旋转数组问题,分治思想:将数分下右上左依次输入到二维数组中间,最后输出。
分治法查找最小值代码,C语言编写,可能需要用input.txt输入,分治法查找最小值代码
题目: 编程实现找出一组数的最大值和次大值 要求: 用二分法的策略实现; (2)写出实验报告。 一、 需求分析: 1、输入要输入数组元素的个数,为数组分配存储空间(动态数组); 2、输入数组元素; 3、利用二分法...
分治法介绍和一个简单的例子 希望对大家有所帮助