Python 解LeetCode：33. Search in Rotated Sorted Array
2024-10-06 16:25:02
题目描述：在一个旋转数组中查找给定的值，其中旋转数组中不含重复值；
思路：
- 第一遍二分遍历，找到数组中最小值的索引；
- 第二遍分别对最小值左右两边的数组进行二分查找；
class Solution(object):
def find_min(self, nums):
if not nums:
return -1
left, right = 0, len(nums) - 1
while nums[left] > nums[right]:
if right - left == 1:
return right
mid = (left + right) / 2
if nums[left] <= nums[mid]:
left = mid
if nums[right] >= nums[mid]:
right = mid
return 0
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return -1
min_index = self.find_min(nums)
if nums[min_index] == target:
return min_index
elif nums[min_index] > target:
return -1
else:
left = self.search_t(nums, 0, min_index, target)
if left >= 0:
return left
right = self.search_t(nums, min_index, len(nums)-1, target)
if right >= 0:
return right
return -1
def search_t(self, nums, left, right, target):
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
最新文章
- 计算 TP90TP99TP...
- 一个被称为世界上最短的判断IE方法
- SpringMVC 通过post接收form参数或者json参数
- Hibernate-org.hibernate.QueryException: could not resolve property: code of:
- Windows内存小结（有好多图，比较清楚）
- 初识Python-web框架的这两天
- RDC去省赛玩前の日常训练 Chapter 2
- Pytorch系列教程-使用Seq2Seq网络和注意力机制进行机器翻译
- Python 之 type方法创建类
- sqoop无法导出parquet文件到mysql
- Android DevArt1：假设当前Activity为A,如果这时用户打开一个新的Activity B,那么B的onResume和A的onPause哪个先执行呢？
- 使用css方法使footer保持在页面的最底部
- 注册表禁用和启用USB端口
- TraceLog.cs 累积 C#
- Linux远程桌面实现（转）
- js小功能实现
- 结合Bootbox将后台JSON数据填充Form表单
- less 应用
- ALTERA DDRII IP核使用
- MongoDB整理笔记の索引