题目11:旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾, 我们称之数组的旋转。输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素。
举例说明
数组{3,4,5,1,2}
为{1,2,3,4,5}
的一个旋转,该数组的最小值为1。
思路
一. 顺序遍历
首先能想到的就是顺序遍历,数组中最小的元素即为整个旋转数组的最小元素,但算法时间复杂度为O(n)
二. 二分
有序数组的查找大部分离不开二分。
由旋转数组的特性,因为经排序好的数组旋转得到的,所以由其特性可以知道,除了不旋转的情况(即原数组),旋转数组可以划分为两个排序的子数组,前面的子数组元素均大于后面的子数组元素,存在分界线,所以可以想到的就是利用二分查找法,实现时间复杂度为O(logn)
步骤
牢记:要求的是如果发生过旋转,第二个数组的第一个数
。
1. 设置两个指针low,high
low指向数组的开始位置,也就是第一个数组的开始位置
high指向数组的终止位置,也就是第二个数组的结束位置
Mid在中点
2. 比较mid与low,high位置的数组值
一直逼近第二个数组的第一个数。
mid与low,high初始数组值关系- 如果中间位置mid的数大于low指向的数,则mid在第一个数组中。故让low指向mid所指向的数,low指向的依然是数组1的数
- 如果中间位置mid的数小于high所指向的位置,则mid在第二个数组中。故让high指向mid指向的数,high指向的依然是数组2的数
- 知道low和high只差1(相邻),high指针的数组值就是所求
注意考虑以下几种情况的处理:
- 数组元素为空的情况(返回0)
- 数组元素只有一个的情况(返回该元素)
- 数组旋转0个元素,也就是没有旋转的情况,(最后返回mid对应的值,所以初始时令mid=low,遇到该情况while条件不成立,依然返回mid对应的值)
- 如果mid的数既等于p1位置数,又等于p2位置的数,这时候不能确定移哪个指针,就必须采用顺序查找的方法来寻找最小数
如,排序数组为{0,1,1,1,1},旋转数组为{1,0,1,1,1}或者{1,1,1,0,1},当为这两种情况时,mid=low=high,无法确定最小的元素在左还是在右,所以这个时候就需要采用顺序查找的方式。
代码实现
public class _11 {
public static int min(int[] arr) {
if (arr == null||arr.length< 1) {
throw new RuntimeException("Invalid input.");
}
if ( arr.length ==1) {
return arr[0];
}
int low = 0;// 开始处理的第一个位置
int high = arr.length - 1;// 开始处理的最后一个位置
int mid = low;// 设置初始值
// 确保low在前一个排好序的部分,high在排好序的后一个部分
while (arr[low] >= arr[high]) {//没中while就返回mid(low)
if (high - low == 1) {
return arr[high];
}
mid = low + (high - low) / 2;
// 如果三个数都相等,则需要进行顺序处理,从头到尾找最小的值
if (arr[mid] == arr[low] && arr[high] == arr[mid]) {
return minInorder(arr, low, high);
}
if (arr[mid] >= arr[low]) {// 如果arr[mid]在前一个排好序的部分
low = mid;
}
else if (arr[mid] <= arr[high]) {// 如果arr[mid]在后一个排好序的部分
high = mid;
}
}
return arr[mid];
}
private static int minInorder(int[] numbers, int start, int end) {//顺序处理
int result = numbers[start];//想象一个pivot拉低整条线
for (int i = start + 1; i <= end; i++) {
if (result > numbers[i]) {
result = numbers[i];
}
}
return result;
}
public static void main(String[] args) {
// 典型输入,单调升序的数组的一个旋转
int[] array1 = {3, 4, 5, 1, 2};//1
System.out.println(min(array1));
// 有重复数字,并且重复的数字刚好的最小的数字
int[] array2 = {3, 4, 5, 1, 1, 2};//1
System.out.println(min(array2));
// 有重复数字,但重复的数字不是第一个数字和最后一个数字
int[] array3 = {3, 4, 5, 1, 2, 2};//1
System.out.println(min(array3));
// 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
int[] array4 = {1, 0, 1, 1, 1};//0
System.out.println(min(array4));
// 单调升序数组,旋转0个元素,也就是单调升序数组本身
int[] array5 = {1, 2, 3, 4, 5};//1
System.out.println(min(array5));
// 数组中只有一个数字
int[] array6 = {2};//2
System.out.println(min(array6));
// 数组中数字都相同
int[] array7 = {1, 1, 1, 1, 1, 1, 1};//1
System.out.println(min(array7));
// 输入NULL
System.out.println(min(null));//java.lang.RuntimeException: Invalid input.
}
}
输出:
1
1
1
0
1
2
1
Exception in thread "main" java.lang.RuntimeException: Invalid input.
网友评论