当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程之美-数组的最大值和最小值-分治法(两种形式)

发表于: 2012-07-21   作者:bylijinnan   来源:转载   浏览:
摘要: 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[]

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;
	}
	
}

编程之美-数组的最大值和最小值-分治法(两种形式)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
寻找一个数组里的最大值和最小值 法一: 分别遍历一遍,次数O(2*N); 法二: 根据书上的讲述, 法三
方法1:暴力方法 遍历一遍数组,比较2*N次求出最大值和最小值 方法2:改进方法 (破坏了原数组) 遍
转自:http://blog.csdn.net/flyinghearts/article/details/6388834# 问题:寻找数组中的最小值和最
一个有N个整数元素的一位数组(A[0],A[1],A[2],...,A[n-1]),这个数组当然有很多子数组,那么
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
题目: 有一个无序、元素个数为2n的正整数数组,要求:如何能吧这个数组分割为元素个数为n的两个数
编程之美 2.17 数组循环移位 把一个含有N个元素的数组循环右移K位, 要求时间复杂度位O(N), 且只允许
编程之美上面提供了很好的思路,那么我就用代码实现,我这个代码实现可以循环左移和循环右移 // Per
最近一直看编程之美,想法真的很重要,今天发这篇文章还是有一点不自信,希望碰到志同道合的同学一
最近一直看编程之美,想法真的很重要,今天发这篇文章还是有一点不自信,希望碰到志同道合的同学一
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号