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] 时，表示，左侧已经排好序了，右侧没有，最小值一定出现在右侧。
当 nums[mid] < nums[end] 时，表示，右侧已经排好序了，左侧没有，最小值一定出现在左侧。
然后利用这个规则，还用 binary search 的思想，不断递归，直到找到最小值。
算法复杂度是 O(log n)
**
总结： 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!
