本文共 1421 字,大约阅读时间需要 4 分钟。
给定一个旋转数组(将某一升序数组以某一位置旋转而得)nums,要求找出数组中的最小值。规定:数组中没有重复的数字。例子:
可以采用二分查找的思路来做。
首先是两种特殊情况:
对于非特殊情况,我们初始化 start = 0, end = nums.length - 1。计算得到 mid = (start + end)/ 2 。判断nums[mid]与其左右两边的值大小情况:
需要注意的是:在上述的1和2情况,还得需要判断 mid + 1 以及 mid - 1是否越界。(如果越界,则表明可判断正确,即最小或者最大值在左边界或右边界)
class Solution { public int findMin(int[] nums) { if (nums.length == 1 || nums[0] < nums[nums.length - 1]) return nums[0]; int start = 0, end = nums.length - 1; // 因为最小的数肯定存在 所以肯定会在while循环中找到这个数 while (start <= end) { int mid = (start + end) / 2; // 找到最小值 if ((mid + 1 > end || nums[mid] < nums[mid + 1]) && (mid - 1 < start || nums[mid] < nums[mid - 1])) return nums[mid]; // 找到最大值 最大值的下一个数为最小值 如果可以确定当前值为最大值,则最大值肯定不会在nums.length - 1位置处,因为这种情况即为数组已经是升序 在之前已经判断过了 if ((mid + 1 > end || nums[mid] > nums[mid + 1]) && (mid - 1 < start || nums[mid] > nums[mid - 1])) return nums[mid + 1]; if (nums[mid] > nums[0]) start = mid + 1; else end = mid - 1; } return 666; }}
对于这个内存使用,我也是醉了...
转载地址:http://qxesi.baihongyu.com/