您现在的位置是:首页 >技术交流 >Leetcode33.搜索旋转排列数组网站首页技术交流
Leetcode33.搜索旋转排列数组
简介Leetcode33.搜索旋转排列数组
一、题目描述:
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
-
示例 1:
- 输入:nums = [4,5,6,7,0,1,2], target = 0
- 输出:4
-
示例 2:
- 输入:nums = [4,5,6,7,0,1,2], target = 3
- 输出:-1
-
示例 3:
- 输入:nums = [1], target = 0
- 输出:-1
- 提示:
- 1 ≤ n u m s . l e n g t h ≤ 5000 1 leq nums.length leq 5000 1≤nums.length≤5000
- − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 leq nums[i] leq 10^4 −104≤nums[i]≤104
- nums 中的每个值都 独一无二
- − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4 leq target leq 10^4 −104≤target≤104
二、解决思路和代码
1. 解决思路
- 分析:分两步解决:分割,查找,这两个步骤都使用二分查找的方法
- 分割:将旋转数组分割为两个递增的数组【二分查找索引】
- 查找:对比 target 与 nums[0] 两个数值的大小,确定在哪一个递增数组中进行查找【二分查找目标值】
2. 代码
from typing import *
class Solution:
def getIndex(self, nums:List[int]) -> int:
left, right = 0, len(nums)-1
while left<=right:
mid = (left+right)//2
if nums[mid]>nums[left] and nums[mid]>nums[right]:
left = mid
elif nums[mid]<nums[left] and nums[mid]<nums[right]:
right = mid
else:
return left if nums[left]<nums[right] else right
return -1
def binarySearch(self,nums:List[int], target:int, start:int, end:int) -> int:
while start<=end:
mid = (start+end)//2
if nums[mid]<target:
start = mid+1
elif nums[mid]>target:
end = mid-1
else:
return mid
return -1
def search(self, nums: List[int], target: int) -> int:
start = self.getIndex(nums)
if start == -1 or start==0:
return self.binarySearch(nums,target,0,len(nums)-1)
if target>=nums[0]:
return self.binarySearch(nums,target,0,start-1)
else:
return self.binarySearch(nums,target,start,len(nums)-1)
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。