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

java-69-旋转数组的最小元素。把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素

发表于: 2012-02-29   作者:bylijinnan   来源:转载   浏览:
摘要: public class MinOfShiftedArray { /** * Q69 旋转数组的最小元素 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。 * 例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。 */ publ

public class MinOfShiftedArray {

	/**
	 * Q69 旋转数组的最小元素
	 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。
	 * 例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。
	 */
	public static void main(String[] args) {
		int[][] a={
				{1,2,3,4,5},
				{2,3,4,5,1},
				{3,4,5,1,2},
				{4,5,1,2,3},
				{5,1,2,3,4},
		};
		for(int[] each:a){
			int min=minOfShiftedArray(each);
			System.out.println(min);
		}
	
		
	}

	/*
	 * Divide and conquer
	 */
	public static int minOfShiftedArray(int[] x){
		if(x==null||x.length==0){
			return -1;
		}
		int len=x.length;
		int low=0;
		int high=len-1;
		if(x[low]<x[high]){//if the array is not shifted actually,e.g. {1,2,3,4,5}
			return x[low];
		}
		int mid=0;
		while(low<high){
			mid=(low&high)+(low^high)/2;
			if(mid==low){//if there are only two elements left
				return x[low]<x[high]?x[low]:x[high];
			}
			if(x[mid]>x[low]){
				low=mid;
			}else{
				high=mid;
			}
		}
		return x[mid];
	}
}

java-69-旋转数组的最小元素。把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号