月度归档:2013年12月

LeetCode:Search in Rotated Sorted Array II

接前一题(Search in Rotated Sorted Array),但数组中的元素允许重复。
LeetCode OJ地址:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
关键点:旋转前数组有序,可能有重复元素。


我的解法:
前一题能利用折半查找思想的关键是旋转后数组分为两个有序子区间,可以通过A[first]A[mid]A[last-1]target的大小测试来快速缩小查找范围。由于本题中数组可能有重复元素,如对于数组[1,3,1,1,1]A[first]=A[mid]=A[last-1]=1,此时将无法确定是应该将查找区间搜小到A[first,mid)还是A[mid+1,last)。
因此,算法加入高亮代码行17和18的判断,当这三个元素相等时,只++first
注:search返回值由位置索引int修改为是否存在标识bool
// 时间复杂度O(n),空间复杂度O(1)
class Solution {