p154

发表于 | 分类于 |

LeetCode p154 Find Minimum in Rotated Sorted Array II 题解

1.题目：

Suppose a sorted array 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.

题意：

折断旋转的有序数组，找到最小数。

2.解题思路:

二分查找

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public class Solution {
    public int findMin(int[] nums) {
        if (nums.length < 1)
			return 0;
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < nums[right])
				right = mid;
			else {
				if (nums[mid] > nums[right]) {

					left = mid + 1;
				} else {
					right--;
				}
			}
		}
		return nums[left];
    }
}

4.一些总结：