剑指 offer——面试题8求旋转数组的最小值

题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。

这本质上是一个求最值的问题,最简单的方法就是顺序遍历数组,从中找出最小值,该方法的时间复杂度为O(n)。但这种方法会被面试官鄙视的,所以我们寻找更为高效的办法。

这道题给的数组是一个“旋转数组”,旋转数组是将一个非递减数组切成两个数组后重新组装而成的,旋转数组的前半段所有元素值均大于等于后半段元素的值,两段的分界点就是最小值。

要寻找分界点,可以采用对半搜索,若第一个元素的值小于中点元素值,则断点在后半段,否则断点在前半段,若当前数组只剩下两个元素时,找出其中较小一个即是答案。时间复杂度为O(logn)。

下面我们来考虑一些特殊情况:

  1. 若序列本身有序,若仍然采用上述算法,则会将倒数第二个元素误判为最小值。因此,如果数组的第一个元素小于最后一个元素时就认为数组有序,第一个元素即为最小值。
  2. 若数组的第一个元素和最后一个元素相等,则断点可能在中点的前半段,也可能在后半段,此时需要遍历数组求得最小值。
/**
 * 获取旋转数组的最小值
 * 旋转数组:在一个递增数组的任意一个位置切一刀,
 * 	再把第一个数组放到第二个数组的后面,
 * 	这样生成的数组就是旋转数组。 
 * @author chibozhou
 */
public class GetMin {
	private static int min;
	/**
	 * 获取旋转数组的最小值
	 * @param arr 输入的旋转数组
	 * @param start 数组的起始下标
	 * @param end 数组的结束下标
	 * @param min 搜索结果最小值
	 */
	public static void getMin(int[] arr,int start,int end,Int min){
		//健壮性判断,数组不能为空
		if(arr==null || arr.length<=0){
			System.out.println("数组为空!");
			return ;
		}
		//健壮性判断,start不能>end
		if(start<0 || end<0 || start>end){
			System.out.println("start、end非法!");
			return;
		}
		//健壮性判断,min不能为空
		if(min==null){
			System.out.println("min为空!");
			return;
		}
		
		//若数组首<尾,则本身有序
		if(arr[start]<arr[end]){
			System.out.println("数组本身有序");
			min.setMin(arr[start]);
			return;
		}
		
		//若数组首=尾,则断点位置不确定
		if(arr[start]==arr[end]){
			//遍历数组,寻找最小值
			int i = start;
			while(arr[i]<=arr[i+1] && i<end){
				i++;
			}
			//输出最小值
			min.setMin(arr[++i]);
		}
		
		//若数组首>尾,则断点位置可以确定(要么在中点前,要么在中点后)
		if(arr[start]>arr[end]){
			//获取中点
			int mid = (start+end)/2;
			//若数组首<中点,则断点在后半段
			if(arr[start]<arr[mid]){
				start = mid+1;
			}
			else if(arr[start]>arr[end]){
				end = mid-1;
			}
			else{//arr[start]=arr[end]
				start = mid+1;
			}
			
			//若start和end相邻,则比较一下选出小的
			if(start+1==end){
				if(arr[start]>arr[end]){
					min.setMin(arr[end]);
				}
				else{
					min.setMin(arr[start]);
				}
				return;
			}
			getMin(arr,start,end,min);
		}
	}
	
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		int[] a = new int[]{5,5,5,1,1,1,2,3,4};
		Int min = new Int();
		getMin(a, 0, a.length-1, min);
	}
}
<pre code_snippet_id="1600005" snippet_file_name="blog_20160307_4_6262722" name="code" class="java">/**

* 本类用于设置最小值 * @author chibozhou */class Int{private int min;public int getMin() {return min;}public void setMin(int min) {this.min = min;}}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

1062
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

1002
来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

1003
来自专栏CDA数据分析师

入门 | 一文带你了解Python集合与基本的集合运算

了解 Python 集合: 它们是什么,如何创建它们,何时使用它们,什么是内置函数,以及它们与集合论操作的关系

1090
来自专栏数据结构与算法

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

2905
来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

3327
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

782
来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

711
来自专栏北京马哥教育

python3急速入门 (二) 列表的使用

云豆贴心提醒,这是马哥Linux运维Python3急速入门系列第1篇文章 列表用于组织其它数值,即写在方括号之间、用逗号分隔开的数值列表。列表内的项目不必全是...

2975
来自专栏静默虚空的博客

排序算法系列

概述 概念 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 排序分为内部排序和外部排序。 若整个排序过程不需要访问...

2327

扫码关注云+社区

领取腾讯云代金券