[剑指offer]面试题第[6]题[JAVA][旋转数组的最小数字][二分法]

####【问题描述】

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

####【解答思路】

1.使用-.sort()

public class Solution {public int minNumberInRotateArray(int [] array) {if (array.length == 0)return 0;Arrays.sort(array);return array[0];}

2.巧妙利用旋转特性

import java.util.ArrayList;public class Solution {public int minNumberInRotateArray(int[] array) {if (array.length == 0)return 0;for (int i = 0; i < array.length - 1; i++) {if (array[i] > array[i + 1])return array[i + 1];}return array[0];} }

3.二分法 变种

import java.util.ArrayList;public class Solution {public int minNumberInRotateArray(int [] array) {int low = 0 ; int high = array.length - 1; while(low < high){int mid = low + (high - low) / 2; if(array[mid] > array[high]){low = mid + 1;}else if(array[mid] == array[high]){high = high - 1;}else{high = mid;} }return array[low];}}

【总结】

写一个好的二分法和灵活应用是件不容易的事情

如果觉得《[剑指offer]面试题第[6]题[JAVA][旋转数组的最小数字][二分法]》对你有帮助，请点赞、收藏，并留下你的观点哦！