LeetCode刷题实战81:搜索旋转排序数组 II
共 2451字,需浏览 5分钟
·
2020-10-31 01:08
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 搜索旋转排序数组 II,我们先来看题面:
https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
题意
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
解题
题解
class Solution:
def search(self, nums: List[int], target: int) -> bool:
l, r = 0, len(nums)-1
while l <= r:
m = (l + r) >> 1
if nums[m] == target:
return True
if nums[l] == nums[m]:
l += 1
continue
if nums[l] < nums[m]:
if nums[l] <= target < nums[m]:
r = m - 1
else:
l = m + 1
else:
if nums[m] < target <= nums[r]:
l = m + 1
else:
r = m - 1
return False
总结
上期推文: