Paste_Image.png
My code:
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int minIndex = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] >= nums[i - 1])
continue;
else {
minIndex = i;
break;
}
}
return nums[minIndex];
}
}
My test result:
這不是一個好方法扮授。
下面介紹 binary search 版方法期揪。
My code:
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int minIndex = findMin(0, nums.length - 1, nums);
return nums[minIndex];
}
private int findMin(int begin, int end, int[] nums) {
if (begin == end)
return begin;
int mid = (begin + end) / 2;
if (nums[mid] < nums[end]) // right part is sorted so minimun exists in the left
return findMin(begin, mid, nums);
else // left part is sorted so minimun exists in the right
return findMin(mid + 1, end, nums);
}
}
My test result:
Paste_Image.png
一下子快了好多中贝。
上一種算法復雜度是O(n), 而這個復雜度是 O(log n)
上一個算法就是從頭遍歷但两，找到突然開始變小的位置媒熊，就是最小值验残。
仔細介紹該算法。
如上圖所示：
當 nums[mid] > nums[end] 時纠修，表示胳嘲，左側(cè)已經(jīng)排好序了，右側(cè)沒有扣草，最小值一定出現(xiàn)在右側(cè)了牛。
當 nums[mid] < nums[end] 時，表示辰妙，右側(cè)已經(jīng)排好序了鹰祸，左側(cè)沒有，最小值一定出現(xiàn)在左側(cè)密浑。
然后利用這個規(guī)則蛙婴，還用 binary search 的思想，不斷遞歸尔破，直到找到最小值街图。
算法復雜度是 O(log n)
**
總結(jié)： Array, Binary Search
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int begin = 0;
int end = nums.length - 1;
while (begin < end) {
int middle = (begin + end) / 2;
if (nums[middle] < nums[end]) {
end = middle;
}
else { // nums[middle] >= nums[end] which means nums[middle] is not the absolute minimum elem
begin = middle + 1;
}
}
return nums[begin];
}
}
沒什么難的。主要在一個地方思考了下懒构。
當 nums[middle] < nums[end]時餐济，end = middle.
But, 當nums[middle] >= nums[end]時， begin = middle + 1, 因為nums[middle]一定不是唯一的那個最小值胆剧。所以可以排除他絮姆，進一步縮小范圍。
Anyway, Good luck, Richardo!
