首页 > 代码库 > leetcode 【 Search in Rotated Sorted Array II 】python 实现
leetcode 【 Search in Rotated Sorted Array II 】python 实现
题目：
与上一道题几乎相同；不同之处在于array中允许有重复元素；但题目要求也简单了，只要返回true or false
http://www.cnblogs.com/xbf9xbf/p/4254590.html
代码：oj测试通过 Runtime: 73 ms
1 class Solution: 2 # @param A a list of integers 3 # @param target an integer 4 # @return a boolean 5 def search(self, A, target): 6 A=list(set(A)) 7 # none case & zero case 8 if A is None or len(A)==0 : 9 return False10 # binary search11 start = 012 end = len(A)-113 while start<=end :14 # one element left case15 if start == end :16 if A[start]==target :17 return True18 else:19 return False20 # two elements left case21 if start+1 == end :22 if A[start]==target :23 return True 24 elif A[end]==target :25 return True26 else:27 return False28 # equal or more than three elements case29 mid = (start+end)/230 if A[mid]==target :31 return True32 elif A[mid]>target:33 if A[start]>A[mid] and A[end]<A[mid]:34 start = mid+135 elif A[start]<A[mid] and A[end]<A[mid]:36 if A[end]>=target:37 start = mid+138 else:39 end = mid-140 elif A[start]>A[mid] and A[end]>A[mid]:41 end = mid-142 else:43 end = mid-144 else:45 if A[start]>A[mid] and A[end]<A[mid]:46 end = mid-147 elif A[start]<A[mid] and A[end]<A[mid]:48 start = mid+149 elif A[start]>A[mid] and A[end]>A[mid]:50 if A[end]>=target :51 start = mid+152 else:53 end = mid-154 else:55 start = mid+156 return False
思路：
用了一个trick Python数组去重的办法A=list(set(A))
这样A数组中就没有重复的元素了，可以直接用之前一题的代码。
这样的trick应该不是题目的本意，这道二分查找题目比较经典，应该吃透。
leetcode 【 Search in Rotated Sorted Array II 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。