文章目錄
  1. 1. 题目
  2. 2. 说明
  3. 3. 解法
  4. 4. 代码

题目

一个数组是以循环顺序排列的,也就是说在数组中有某个元素i,从x[i]开始有这样的关系,即x[0] < x[1] < x[2] < … < x[i - 1],x[i] < x[i + 1] < … < x[n] < x[0]。例如8,10,14,15,2,6这7个元素就是循环顺序排列的,因为从2开始为递增,到了最后一个元素就转化为第1个元素,再一次顺序递增。换句话说,如果把x[i],x[i + 1],…,x[n]取出,并且接到数组开头,于是就是一个从小到大的顺序(这不是个旋转的工作吗?)。编写一个程序,接收一个以循环顺序排列的数组,把它的极小值找出来,以上面的数据为例,程序应该会输出2.

说明

因为从x[0]起顺序是递增的,一直到极小值出现,马上就会出现相反的顺序,于是很多人马上就会想出这个做法:
for (i = 1; i < n && x[i] >= x[i - 1]; i++)
一旦这个循环停下来了,如果i等于n那就表示每一个元素都大于在它前面的哪一个,因而极小值为x[0];但若i < n,且x[i] < x[i - 1],因此极小值为x[i]。
这是个正确的做法,但效率却不够高,因为在最坏的情况下可能要做n - 1次的比较。不过,这个数组严格说还是有顺序性的,根据这一特性应该可以找出更好、更快的方法,不妨试试看。

解法

解决的办法是用二分查找。也许会质疑这个数组并没有完全依顺序排列,所以不能用二分查找法。其实只要能够把问题分成两部分,而有办法判断解答在其中一部分的话,这就是个二分查找。

现在处理x[L]与x[R]之间的元素(包含两个端点),去中间元素x[M], M = (R - L) / 2 + L,会出现以下两中情况

  1. x[M] < x[R],因为从左到右是递增的,直到极小值开始才下降,之后又开始递增。而第一个递增部分的任意一个元素大于第二个递增部分的任意元素。所以极小值一定不会在M的右边。所以下一个R = M。
  2. x[M] >= x[R],会出现这种情况,说明M在第一个递增部分,R在第二个递增部分,所以极小值一定在M的右边。所以下一个L = M + 1。

就这样一直反复下去,等到L=R的时候, x[L]就是极小值。

代码

写成代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class MinimumInRotatedSortedArray {
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int mid = 0;
while (left < right) {
mid = (right - left) / 2 + left;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}

public static void main(String[] args) {
int[] temp = {6, 7, 1, 2, 3, 4};
System.out.println(findMin(temp));
}
}

文章目錄
  1. 1. 题目
  2. 2. 说明
  3. 3. 解法
  4. 4. 代码