前言
【LeetCode 题解】系列传送门：
http://www.cnblogs.com/double-win/category/573499.html
题目描述
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
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
# 题意
假设有一个有序的循环数组， 其起始位置未知。
如 序列```0 1 2 4 5 6 7``` 可能的数组形式为 ```4 5 6 7 0 1 2```
给定一个目标数据，查找该数据是否在给定的数组中出现。 如果在数组中找到该目标数据，则返回该目标数据所在的数组下标， 否则返回-1.
Tips: 假设给定的数组中没有重复的元素
# 思路
根据题意提取关键信息： 在一个***sorted array***中查找给定元素
首先能够想到的是binary search。 由于数组是一个循环数组， 那么数组的最小值和最大值并不一定分别在数组两端。
（1） 思路一： 从头到尾，依次遍历数组， 查找目标元素， 其时间复杂度O(n)
（2） 思路二： 从头到尾寻找min， max， 然后将左侧较大的数据concat到右侧， 然后再用binary search。 时间复杂度 O(n/2) + O(logn) ~ O(n)
（3） 思路三：如果将原始数组分割成左右两半， 可以发现其具有如下几种情形：
> case 1: 最小值和最大值分别在左右两侧：
> ```leftpart: [0 1 2 4] rightpart:[5 6 7]```
> 值得注意的是该情况最大值只能在最右侧， 且最小值只能在最左侧
> case 2：
> 最大值和最小值同侧： 最大值在右侧
> ```leftpart: [ 2 4 5 6] rightpart: [7 0 1]```
> 可以发现 leftValue = 2 medianValue = 6 rightValue = 1
> medianValue > leftValue && medianValue > rightValue:
> 如果 target > medianValue 或者 target < rightValue， 那么必在rightpart
> 否则，必在leftpart
> case 3:
> 最大值和最小值同侧： 最小值在左侧
> ```leftpart: [6 7 0 1] rightpart: [2 4 5]```
> 可以发现 leftValue = 6 medianValue = 1 rightValue = 5
> medianValue < leftValue && medianValue < rightValue:
> 如果 target < medianValue 或者 target > rightValue， 那么必在leftpart
> 否则，必在rightpart
加上一些边界条件，即得结果。
# 解法
```python
class Solution(object):
def findTarget(self, nums, minIndex, maxIndex, target):
"""
:type nums: List[index]
:type minIndex: int
:type maxIndex: int
:type target: int
:rtype: int
"""
if nums[minIndex] == target:
return minIndex
if nums[maxIndex] == target:
return maxIndex
if maxIndex == minIndex:
return 0 if target == nums[minIndex] else -1
median = (minIndex + maxIndex) / 2
if nums[median] == target:
return median
if nums[median] > nums[minIndex] and nums[median] > nums[maxIndex]:
# maxValue and minValue is in right part
if target > nums[median] or target < nums[minIndex]:
return self.findTarget(nums, median + 1, maxIndex, target)
else:
return self.findTarget(nums, minIndex, median, target)
elif nums[median] < nums[minIndex] and nums[median] < nums[maxIndex]:
# maxValue is in left part
if target < nums[median] or target > nums[maxIndex]:
return self.findTarget(nums, minIndex, median, target)
else:
return self.findTarget(nums, median + 1, maxIndex, target)
else:
# maxValue is in maxIndex and minValue is in minIndex
if target < nums[minIndex] or target > nums[maxIndex]:
return -1
elif target > nums[median]:
return self.findTarget(nums, median + 1, maxIndex, target)
else:
return self.findTarget(nums, minIndex, median, target)
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
numSize = len(nums)
# the array is empty
if numSize == 0:
return -1
minIndex = 0
maxIndex = numSize - 1
return self.findTarget(nums, minIndex, maxIndex, target)
声明
| 作者 | Double_Win |
| 出处 | http://www.cnblogs.com/double-win/p/7966913.html |
| 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接，否则作者保留追究法律责任的权利。 若本文对你有所帮助，您的关注和推荐是我们分享知识的动力! |