【leetcode】154. find minimum in rotated sorted array ii

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int (int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < nums[high]) {
high = mid;
} else if (nums[mid] > nums[high]) {
low = mid + 1;
} else {
high--;
}
}
return nums[low];
}

Result

AC

Analyse

这里分析的结果是,如果nums[mid] == nums[high]的话,很容易会出现TLE,那么在判断的情况下增加一个判断nums[mid] == nums[high]的话,high–,可以结束出while条件。