旋转数组的最小数字

  • 题目描述:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

  • 解题思路:

①最直接的方法:遍历数组,直接从中找出最小值,时间复杂度为O(n)
②根据旋转数组的特点,可以将旋转后的数组划分为两个子数组,分别是未经旋转的元素和旋转的元素。由于两个子数组都是非递减排列的,所以待求最小元素即位于两个子数组的交界处,这样可以利用二分查找算法来进行查找,时间复杂度为O(logn)
存在以下几种情况:
a: 如果数组的0个元素发生旋转,那么数组序列未发生改变,最小元素即为原数组的第一个元素
b: 如果数组的部分元素发生旋转,利用二分查找算法来找出最小元素
c: 题目要求数组为非递减排序,可能会出现重复元素,其中存在一种特例无法使用二分查找算法,即数组中间元素与首元素及末尾元素均相等时,无法判断出中间元素是属于哪一部分,此时可以通过直接遍历数组的方式找出最小元素。

  • 源代码:
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
36
37
38
39
40
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int size = rotateArray.size();
if (size == 0)
return 0; //若数组大小为0,返回为0
int left =0;
int right = size-1;
int mid = 0; //若数组的0个元素发生旋转,最小元素即为数组的第一个元素
while (rotateArray[left] >= rotateArray[right]) {
//一般情况下,数组部分元素发生旋转时,旋转后的数组首元素>=尾部元素
if (right-left == 1) {
mid = right; //当数组只有两个元素时,最小元素即为尾部元素,不必再继续查找
break;
}
if (rotateArray[left] == rotateArray[mid] && rotateArray[right] == rotateArray[mid]) {
//特例,此时无法判断中间元素的具体位置,无法利用二分查找,可以使用直接遍历数组的方式寻找最小元素
return MinOrder(rotateArray,left,right);
}
mid = (left+right)/2;
if (rotateArray[mid] >= rotateArray[left]) {
left = mid;
}
else if (rotateArray[mid] <= rotateArray[right]) {
right = mid;
}
}
return rotateArray[mid];
}
//直接遍历数组找最小值的方法
int MinOrder(vector<int> array,int left,int right) {
int result = array[left];
for (int i = left+1;i<=right;i++) {
if (array[i] < result) {
result = array[i];
}
}
return result;
}
};
-------------The End-------------