题目描述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如:数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
思路与代码:
- 直接按照题意扫描一遍数组,找到最小的值
- 分析:下意识想到的傻瓜办法,训练思维没啥 * 用,时间复杂度O(n)
public int minNumberInRotateArray(int[] array) {
int len = array.length;
if (len == 0) return 0;
for (int index = 1; index < 8; index++) {
if (array[0] > array[index]) {
return array[index];
}
}
return array[0];
}
- 二分法查找最小值
- 分析:数组是由两个非减序列组成,可以当作“有序数组”,这类有序数组查找某值【最小值】的问题可以想到使用二分法来做,时间复杂度O(logn)
public int minNumberInRotateArray(int[] array) {
int len = array.length;
if (len == 0) return 0;
int left = 0;
int right = len - 1;
int mid = (left + right) / 2;
while (left < right) {
if (array[left] < array[right]) {
right = mid;
//System.out.println("left = "+array[left]);
//System.out.println("right = "+array[right]);
}
if (array[left] > array[right]) {
left = mid;
//System.out.println("left = "+array[left]);
//System.out.println("right = "+array[right]);
}
mid = (left + right) / 2;
}
return array[mid];
}
Attention:
- 非降/减序排序:呈升/增序分布,允许存在相同大小的值。[eg: 1 , 2 , 3 , 3 , 5 , 9 ]
- 非升/增序排序:呈降/减序分布,允许存在相同大小的值。[eg: 9 , 5 , 3 , 3 , 2 , 1 ]
- 降/减序排序:呈降/减序分布,不存在相同大小的值。[eg: 9 , 5 , 3 , 2 , 1 ]
- 升/增序排序:呈升/增序分布,不存在相同大小的值。[eg: 1 , 2 , 3 , 5 , 9 ]