问题:《编程之美》page166. 寻找数组中的最大值,最小值。
public class MinMax {
/**
* @author:lilywangcn
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array=new int[]{12,34,54,43,23,11,10,9,9,10,9,10};
int[] result=find(array);
System.out.println("min is " + result[0]+", max is " + result[1]);
result=merge(array,0,array.length-1);
System.out.println("min is " + array[result[0]]+", max is " + array[result[1]]);
}
/*
算法设计:直接比较,需要比较2n次
*/
public static int[] find(int[] array){
int min=array[0];
int max=array[1];
for(int i=1;i<array.length;i++){
if(min>array[i]) min=array[i];
if(max<array[i]) max=array[i];
}
int[] result=new int[2];
result[0]=min;
result[1]=max;
return result;
}
/*
算法设计:分治方法比较。类似比赛中的淘汰赛,最后胜出者一定是最好的。两两相比,取其小(大)者,再互相比较,z比较次数:1.5n-2。
*/
public static int[] merge(int[] array, int start, int end){
int[] result=new int[2];
if(start==end){
result[0]=result[1]=start;
return result;
}else{
int[] left=merge(array,start,(start+end)/2);
int[] right=merge(array,(start+end)/2+1,end);
if(array[left[0]]<array[right[0]])
result[0]=left[0];
else
result[0]=right[0];
if(array[left[1]]<array[right[1]])
result[1]=right[1];
else
result[1]=left[1];
}
return result;
}
}
分享到:
相关推荐
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
分治算法实验(用分治法查找数组元素的最大值和最小值).doc
最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大值的两个大值,4个最小值数组的两个最小值!不知道是不是分治法,...
。。。
。。。
。。。
。。。
//从两部分的两个最小值中选择小值}b.假设n=2k,比较次数的递推关系式:C(n)=2C(n/2)+2 for n>2C(1)=0, C(2)=1C(n)=C
常规的做法是遍历一次,分别求出最大值和最小值,但我这里要说的是分治法,将数组分成左右两部分,先求出左半部份的最大值和最小值,再求出右半部份的最大值和最小值,然后综合起来求总体的最大值及最小值。...
自己做的一个简单的求一组数据中两个最大的数和两个最小的数,并且求数组的和,然后输出!
2.加深对分治法算法设计方法的理解与应用; 3.锻炼学生对程序跟踪调试能力; 4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。 问题: 输入N个数对其进行归并排序。 解决策略: 分治法策略:...
给定一个顺序表,编写一个求出其最大值和最小值的分治算法。 分析: 由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成。我们知道如果数组大小为 1 则可以直接...
9.1 最小值和最大值 9.2 期望为线性时间的选择算法 9.3 最坏情况为线性时间的选择算法 思考题 本章注记 第三部分 数据结构 第10章 基本数据结构 10.1 栈和队列 10.2 链表 10.3 指针和对象的...
同时获取最大值和最小值,然后分别插入数组的首部和尾部 堆排序 思想 使用大顶堆的思想来排序,每次建堆后交换 做法 总体:建堆-替换 建堆 只要左子树或右子...
7.4 在旋转有序数组中查找最小值 7.4.1 数组无重复 7.4.2 数组有重复 7.5 在旋转排序数组中查找指定数字 8. 暴力枚举法 8.1 求集合的子集 8.2 集合的全排列 8.3 在指定树中选择进行全排列 8.4 电话上对应数字的字母...
3.1.1 从有序数组中查找某个值 3.1.2 假定一个解并判断是否可行 3.1.3 最大化最小值 3.1.4 最大化平均值 3.2 常用技巧精选(一) 3.2.1 尺取法 3.2.2 反转(开关问题) 3.2.3 弹性碰撞 3.2.4 折半枚举(双向搜索) ...