動機
這題是33的follow-up 如果多了重複怎麼辦?
Problem
There is an integer array nums
sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums
is rotated at an unknown pivot index k
(0 <= k < nums.length
) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(0-indexed). For example, [0,1,2,4,4,4,5,6,6,7]
might be rotated at pivot index 5
and become [4,5,6,6,7,0,1,2,4,4]
.
Given the array nums
after the rotation and an integer target
, return true
if target
is in nums
, or false
if it is not in nums
.
You must decrease the overall operation steps as much as possible.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3Output: false
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
is guaranteed to be rotated at some pivot.-104 <= target <= 104
Follow up: This problem is similar to Search in Rotated Sorted Array, but nums
may contain duplicates. Would this affect the runtime complexity? How and why?
Sol
遇到重複就把重複的去掉就好,把與中點重複的去掉就好
def f(ns,n,l,r):
#print(l,r)
if abs(r-l) <= 1:
return ns[l] == n or ns[r] == n
else:
mid = (l+r)//2
if n == ns[mid]:
return True
elif ns[l] < ns[mid]:
if ns[l] <= n and n <= ns[mid]:
return f(ns,n,l,mid)
else:
return f(ns,n,mid+1,r)
elif ns[mid] < ns[r]:
if n >= ns[mid] and n <= ns[r]:
return f(ns,n,mid,r)
else:
return f(ns,n,l,mid-1)
elif ns[l] == ns[mid]:
return f(ns,n,l+1,r)
else:
return f(ns,n,l,r-1)
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return False
return f(nums,target,0,len(nums)-1)