本期帶了了兩道題目，有簡單的先入手。
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [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 的文章
