spss,裙子,八国联军-hi野兽,健身健美社区,锻炼计划推荐

admin 2019-05-21 阅读:297

本文参阅书本 《剑指offer》 作者何海涛

01 标题:数组最小值

把一个数组最开端的若干个元素搬到数组的结尾,咱们称之为数组的旋转。

输入一个递加排序的数组,输出旋转数组的最小元素。例如数组{3,4,5,1,2}是{1,2,3,4,5}的旋转数组,该数组的最小值为1。

02 解题进程

解法1:最直观的解法,便是遍历数组找到最小元素,这种方法的时刻复杂度为o(n)

解法2:递加数组的旋转数组,那么旋转之后的两部分仍然是递加的,如:

咱们能够使用二分查找做此题,取start,end为数组开端和完毕,使得start和end之间不断迫临,直到找到最小值,mid=(start+end)/2

(1)if arr[mid] >= arr[start] 阐明mid值在左边递加数组上,此刻 start=mid,让start趋近最小值

(2)if arr[mid] <= arr[end] 阐明mid定位在右面的递加数组上,此刻 end=mid 向左趋紧最小值

(3) 完毕条件:当start==end-1时完毕判别 end即为此刻的最小值的方位

(4) 判别条件:依照题意 {1,2,3,4,5}也是{1,2,3,4,5}的旋转数组,所以判别条件应该是arr[start] >= arr[end],且初始化mid=start,start=0, end=arr.length-1

03 破例解析

数组 {0,1,1,1,1}的两个旋转数组如下

此数组也是递加数组,可是它的两个旋转数组, 没有办法确认最小值在左边仍是在右面,即arr[start]=arr[mid]=arr[end]时没有办法确认数组最小值在哪边。故此刻只能循环遍历数组。

04 代码完成

public class RotatedArrayMinValue {
/**
* 旋转数组的最小数字
* 把一个数组最开端的若干个元素搬到数组的结尾,咱们称之为数组的旋转。
* 输入一个递加排序的数组,输出旋转数组的最小元素
*/
public static int getMinOfRotateArray (int[] arr) {
if (arr == null || arr.length == 0) {
throw new RuntimeException("数组为空");
}
int start = 0;
int end = arr.length - 1;
int indexMid = start;
while (arr[start] >= arr[end]) {
if (start == end - 1) {
indexMid = end;
break;
}
indexMid = (start + end) / 2;
//无法判别是在左半部分仍是在有半部分
if (arr[start] == arr[indexMid] && arr[end] == arr[indexMid]) {
return getMin(arr, start, end);
}
if (arr[start] <= arr[indexMid]) { // 阐明在前半部分
start = indexMid;
}else if (arr[end] >= arr[indexMid]) { // 阐明在后半部分
end = indexMid;
}
}
return arr[indexMid];
}
public static int getMin(int []arr, int start, int end) {
int min = arr[start];
for (int i = start + 1; i <= end; i ++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
public static void main(String[] args) {
int []arr= new int[]{1,2,3,4,5};
System.out.println(getMinOfRotateArray(arr));
int []arr1= new int[]{1,1,0,1,1};
System.out.println(getMinOfRotateArray(arr1));
int []arr2= new int[]{1,0,1,1, 1};
System.out.println(getMinOfRotateArray(arr2));
int []arr3= new int[]{1,1,1,0,1};
System.out.println(getMinOfRotateArray(arr3));
int []arr4= new int[]{6,7,8,1,2,3,4,5,6};
System.out.println(getMinOfRotateArray(arr4));
int []arr5= new int[]{6};
System.out.println(getMinOfRotateArray(arr5));
}
}