剑指Offer:旋转数组的最小数字

题目

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

NOTE: 给出的所有元素都大于0,若数组大小为0,请返回0。

分析

首先能想到的方法就是遍历一遍数组,就能找到最小的元素。当然如果只是这样的话,这道题也就没有什么价值了。

这道题我们首先要注意观察 旋转 数组的特性。通过观察不难发现,旋转数组可以看做是两个排序的子数组,而且前面子数组的元素大于等于后面子数组的元素,我们还注意到最小的元素正好就在两个子数组的分界线处。

所以,利用这些 特性 ,我们可以用二分查找算法来查找最小元素

我们用两个指针,一个指向数组的第一个元素,一个指向最后一个元素。根据旋转的规则,第一个元素应该是大于等于最后一个元素的(这里存在特殊情况)

接着我们让中间的元素跟这两个元素比较,来确定中间元素是位于前面的子数组还是后面的子数组。如果中间元素大于第一个指针所指向的元素,那就说明它位前面的递增子数组。如果中间元素小于第二个指针所指向的元素,那它就位于后面的递增子数组。随着查找范围的缩小,两个指针会指向连个相邻的元素,而第二个指针指向的正好就是最小的元素。

示例1.jpg

此时两个指针的距离为1,P2指针所指向的元素就是最小元素。

你以为这样就结束了么 太天真了

我们来看下面这个 特例
数组{1,0,1,1,1}和数组{1,1,1,0,1}都可以看做是递增数组{0,1,1,1,1}的旋转。

示例2.jpg

在这两个数组中,第一个、最后一个、中间的元素都是1。因此我们无法确定中间的1到底是属于前面的子数组还是后面的子数组,所以这种情况我们只能通过遍历数组来查找最小元素。

通过上面的分析我们可以得到如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int length = array.length;

int head = 0;
int tail = length - 1;
int mid = head;
while (array[head] >= array[tail]){
if (tail - head == 1){
mid = tail;
break;
}
mid = (head+tail)/2;
// 当head tail mid 所指向的元素相同时,只能遍历查询
if (array[head] == array[tail] && array[head] == array[mid])
return minInOrder(array, head, tail);

if (array[head] <= array[mid])
head = mid;
else
tail = mid;
}
return array[mid];
}
// 处理特殊情况(遍历查询)
public int minInOrder(int[] array, int head, int tail) {
int result = array[head];
for (int i = head+1; i <= tail; i ++) {
if (array[i] < result)
result = array[i];
}
return result;
}
}

这道题告诉我们,考虑问题一定要全面 嗯就是这样~.~

有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%