把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素
输入:[3,4,5,1,2] //这是[1,2,3,4,5]的一个旋转 输出:1 //该数组的最小值为1思路
- 最简单的方式自然是进行遍历记录最小值,这种方式复杂度为O(n)。不过这种方法未利用到旋转数组的特性,因此还有改进空间。
- 旋转本质上就是将原先完全递增的数组取部分子数组嫁接到原数组末尾【当旋转长度为0时即不进行旋转】
- 我们注意到旋转之后的数组实际上可以划分为两个排序的子数组,而且前面子数组的元素都大于等于后面子数组的元素,同时最小的元素正好是两个子数组的分界线,我们以此为基础进行二分查找。
- 令mid=(left+right)/2
- 当arr[mid]>=arr[left]时,说明mid此时指向的位置属于第一个子数组,最小值肯定在mid处或后边,此时令left=mid,缩小查找范围;
- 当arr[mid]<=arr[right]时,说明mid此时指向的位置属于第二个子数组,最小值肯定在mid处或前边,此时令right=mid,缩小查找范围;
- 当right-left==1时,说明此时left指向了第一个子数组的最大值,right指向了第二个子数组的最小值,此时right指向的数值就是我们要找的最小值
- 还有一种特殊情况需要进行考虑,即arr[left]==arr[right]&&arr[left]==arr[mid],此时我们无法辨别mid指向的元素是属于第一个子数组还是第二个子数组,因此无法缩小范围,这种情况下只能使用顺序查找。
public static int minNum(int arr[]) {
// 左右下标
int left = 0, right = arr.length - 1;
int mid = left; // 中间位置下标
while (arr[left] >= arr[right]) {
if (right - left == 1) {
// 说明此时右指针指向最小数
mid = right;
break;
}
mid = (left + right) / 2; // 确立中间位置下标
if (arr[left] == arr[right] && arr[left] == arr[mid]) {
// 若三个下标指向的数字都相等
// 此时无法判断中间数值是属于第一个子数组还是第二个子数组
// 因此此时无法使用二分,只能顺序查找
return minInOrder(arr, left, right);
}
if (arr[mid] >= arr[left]) {
left = mid;
}
if (arr[mid] <= arr[right]) {
right = mid;
}
}
//当旋转长度为0时,数组的第一个元素一定是最小值
return arr[mid];
}
//顺序查找最小值
public static int minInOrder(int arr[], int left, int right) {
int result = arr[left];
for (int i = left + 1; i < right; i++) {
result = Math.min(result, arr[i]);
}
return result;
}
题目来源于《剑指Offer:名企面试官精讲经典编程题》



