Paste_Image.png
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
while (mid - 1 >= begin && nums[mid] == nums[mid - 1])
mid--;
return findMin(begin, mid, nums);
}
else if (nums[mid] > nums[end]){// left part is sorted so minimun exists in the right
int i = mid + 1;
while (i + 1 <= end && nums[i + 1] == nums[i])
i++;
return findMin(i, end, nums);
}
else
return findMin(0, end - 1, nums);
}
}
My test result:
Paste_Image.png
这次题目加了重复，会出现一种情况，即中间等于末尾。
这时，是不确定，最小值在哪侧的。
比如，
3, 3, 1, 3 是在右侧。
再比如，
1, 1, 3, 1 是在左侧。
但是，有一点是确定的，末尾处的值，可能是最小值，但一定不是唯一的最小值。
所以，直接重新处理数组， (begin, end - 1) 即可。
**
总结: Array
**
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;
int i = end;
while (i >= 1 && nums[i] == nums[i - 1])
i--;
if (i == 0)
return nums[0];
else
end = i;
}
else if (nums[middle] > nums[end]){
begin = middle + 1;
int i = begin;
while (i < nums.length - 1 && nums[i] == nums[i + 1])
i++;
if (i == nums.length - 1)
return nums[nums.length - 1];
else
begin = i;
}
else {
end = end - 1;
}
}
return nums[begin];
}
}
这道题目加强了难度。我也是两遍之后才过。
主要是这么一种情况。
3 3 1 3
或者是
1 3 3 3
这种情况下，nums[middle] == nums[end] 但是最小值却出现在不同的地方。
所以不知道该是end = middle 还是 begin = middle + 1, 这是不确定的。
那么就可以直接， end = end - 1,缩短一位，继续寻找。
因为nums[middle] == nums[end], 所以就算nums[end]是最小值，那么还有nums[middle]存在，一定不会把最小值漏掉的。
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 mid = begin + (end - begin) / 2;
if (nums[mid] < nums[end]) {
end = mid;
}
else if (nums[mid] > nums[end]) {
begin = mid + 1;
}
else {
end--;
}
}
return nums[begin];
}
}
reference:
https://discuss.leetcode.com/topic/59136/very-simple-java-solution-based-on-binary-search
much simpler code
Anyway, Good luck, Richardo! -- 09/21/2016
