当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
时间限制:1 秒内存限制:32 兆特殊判题:否 题目描述: 把一个数组最开始的若干个元素搬到数组的末
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增的排序的
题目要求:   把一个不降序数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一
惯例,我们来看一下题目: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输
旋转数组的特点: (1)递增排序的数组旋转之后的数组可划分为两个排序的子数组; (2)前面的子数
题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序
题目: 把一个数组最开始的若干个元素搬到数组的末尾, 我们称之数组的旋转。输入一个递增排序的数
一、题目:旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组
#include <iostream> using namespace std; int main() { int a[9],i; for(i=0;i<9;i++) c
生成一个连续数字的旋转二维数组,起始位置位于左上角,然后从起始位置开始递增,按照顺时针或者逆时
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号