本期带了了两道题目，有简单的先入手。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
和在有序数组中查找指定数一样，这里再旋转数组中查找最小值，可以使用二分法进行查找。代码如下
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
var start = 0;
var end = nums.length - 1;
var mid;
while(true){
mid = Math.floor((start + end) / 2);
if(nums[mid] > nums[start] && nums[mid] > nums[end]){
start = mid;
continue;
}
if(nums[mid] < nums[start] && nums[mid] < nums[end]){
end = mid;
continue;
}
return Math.min(nums[start], nums[end]);
}
};
这里使用floor进行，当然也可以使用ceil，不做累述。实现方案应该都是大同小异。
下面进入第二题。存在重复数时的情况。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5]
输出: 1
示例 2：
输入: [2,2,2,0,1]
输出: 0
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
其实整体思路和第一题一样，同样使用二分法进行查找，但是当出现相等的情况，需要考虑一下。
尤其是三个数据都相等的情况，这种最小值可能在两边的任意一个中，不能直接确定，所以2块都要继续二分查找下去。代码如下
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
var start = 0;
var end = nums.length - 1;
return findMinH(nums, start, end);
};
var findMinH = function(nums, start, end){
if(start + 1 >= end){
return Math.min(nums[start], nums[end]);
}
var middle = Math.floor((start + end) / 2);
if(nums[middle] == nums[start] && nums[middle] == nums[end]){
// 两边都需要继续二分查找
return Math.min(findMinH(nums, start, middle), findMinH(nums, middle + 1, end));
}
if(nums[middle] < nums[start] && nums[middle] < nums[end]){
end = middle;
return findMinH(nums, start, end);
}
if(nums[middle] > nums[start] && nums[middle] > nums[end]){
start = middle;
return findMinH(nums, start, end);
}
if(nums[middle] == nums[start] && nums[middle] > nums[end]){
start =middle;
return findMinH(nums, start, end);
}
if(nums[middle] == nums[end] && nums[middle] < nums[start]){
end =middle;
return findMinH(nums, start, end);
}
return Math.min(nums[start], nums[end]);
};
循序渐进，发现困难难度的题目也能凭自己直接想出解法。是比以前进步了很多。
閱讀更多 儛2018 的文章
