[Lintcode]62. Search in Rotated Sorted Array/[Leetcode]33. S
发布时间:2020-12-14 04:25:22 所属栏目:大数据 来源:网络整理
导读:[Lintcode]62. Search in Rotated Sorted Array/[Leetcode]33. Search in Rotated Sorted Array 本题难度: Medium/Medium Topic: Binary Search Description Search in Rotated Sorted Array Suppose a sorted array is rotated at some pivot unknown to yo
[Lintcode]62. Search in Rotated Sorted Array/[Leetcode]33. Search in Rotated Sorted Array
(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. Example For [4,3] and target=0,return -1. Challenge 我的代码class Solution: def search(self,A: ‘List[int]‘,target: ‘int‘) -> ‘int‘: # write your code here if A == []: return -1 l = 0 r = len(A)-1#注意! f = -1 # breakpoint while(l<=r): m = (l + r) // 2 #print(l,m,r) if A[m]>A[0]: l = m+1 else: #1. m == 0 #2. m == len(A)-1 ok # 不存在需要m==0的情况 # if m == 0: # f = -1 # break if m == 0: if len(A)==1: f = -1 else: if A[0]>A[1]: f = 1 else: f = -1 break if A[m-1]>A[m]:#注意向下取整 f = m break else: r = m-1 #print(f) if f == -1: l = 0 r = len(A) - 1 else: if target>=A[0]: l = 0 r = f-1 else: l = f r = len(A)-1 while(l<=r): m = (l+r)//2 if A[m] == target: return m else: if A[m]>target: r = m-1 else: l = m+1 return -1 别人的代码class Solution: # @param {integer[]} numss # @param {integer} target # @return {integer} def search(self,nums,target): if not nums: return -1 low,high = 0,len(nums) - 1 while low <= high: mid = (low + high) / 2 if target == nums[mid]: return mid if nums[low] <= nums[mid]: if nums[low] <= target <= nums[mid]: high = mid - 1 else: low = mid + 1 else: if nums[mid] <= target <= nums[high]: low = mid + 1 else: high = mid - 1 return -1 思路情况比较多,在处理边界问题上频繁出错。
气死我了,看看人家的思路多好!我真是脑残。 同类问题[Leetcode]81. Search in Rotated Sorted Array II
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |