By

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

题目

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个 排好序的数组的一个旋转,
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数 组的最小值为 1。

解析

该题最容易想到的就是遍历，但是他的复杂度是O(n)，而作为面试题肯定是需要我们找出一种更优的方法

这里使用可以二分法来解决该问题,假设数组a的长度为n，现在使用二分法过程中左端索引s,右端索引t，则中间位置为m=s+(t-s)/2
首先可以知道旋转数组在旋转之后a[0]>a[n-1]是肯定成立的，

当a[s]<=a[m]的时候，我们应该进去右侧继续查找，比如a[0]a[m]的时候 进入左侧继续搜索，直到
可以发现当a[s]<=a[t]的时候 a[s]肯定就是最小值了。

以[1,2,3,4,5,6,7,8]的旋转数组[4,5,6,7,8,1,2,3]为例
第一次搜索
[4,5,6,7,8,1,2,3]
 s     m       t
 此时a[s]<a[m] 进入右侧，则有

[4,5,6,7,8,1,2,3]
         s m   t
此时a[s]>a[m]，进入左侧
[4,5,6,7,8,1,2,3]
        sm t
此时a[s]=a[m] 继续右侧
[4,5,6,7,8,1,2,3]
           st
这里就满足a[s]<=a[t]  则a[s]=1 最小

这样就可以将复杂度降为O(logn) ^_^

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 求旋转数组中最小的值  避免遍历O(n)
 * 可以使用二分法来做
 * [4,5,6,7,8,1,2,3]
 * @param a
 * @param s
 * @param t
 * @return
 */
public static int minValueRatateArray(int[] a,int s,int t)
{
	 if(a[s]<=a[t])
		 return a[s];//其实这个就是最小值了
	 
	 int m=s+(t-s)/2;//中间数
	 if(a[s]<=a[m])
		 return minValueRatateArray(a,m+1,t);//取右边
	 else 
		 return minValueRatateArray(a,s,m);//取左边
	
}

参考

  • July 微软面试100题系列 第69题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考