Leetcode题解-算法-二分法(python版)
2021/5/23 12:25:11
本文主要是介绍Leetcode题解-算法-二分法(python版),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 1、求开方
- 2、找大于给定字符的最小字符
- 3、排序重复数组中找出现一次的数
- 4、第一个出错的版本
- 5、旋转数组最小值
- 6、目标数在排序数组中出现的首尾位置
1、求开方
69. x 的平方根(Easy)
class Solution(object): def mySqrt(self, x): left, right = 1, x while (left <= right): mid = (left + right) // 2 if mid * mid <= x: left = mid + 1 else: right = mid - 1 return right
2、找大于给定字符的最小字符
744. 寻找比目标字母大的最小字母(Easy)
class Solution(object): def nextGreatestLetter(self, letters, target): left, right = 0, len(letters) - 1 while left <= right: mid = (left + right) // 2 if letters[mid] <= target: left = mid + 1 else: right = mid - 1 return letters[0] if left == len(letters) else letters[left]
class Solution(object): def nextGreatestLetter(self, letters, target): index = bisect.bisect(letters, target) return letters[index%len(letters)]
3、排序重复数组中找出现一次的数
540. 有序数组中的单一元素(Medium)
问题分析:
二分法,每次让 mid 位于序号为 0,2,4,6… 的偶数的元素上。
如果目标元素在 mid 右边,一定有 nums[mid]==nums[mid+1],目标元素范围更新为 [mid+2,right];
如果目标元素为 mid 或者在 mid 左边,一定有 nums[mid]!=nums[mid+1],目标元素范围更新为 [left,mid]。
class Solution(object): def singleNonDuplicate(self, nums): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if mid % 2: mid -= 1 if nums[mid] == nums[mid + 1]: left = mid + 2 else: right = mid return nums[left]
时间复杂度:O(log(n/2)) = O(logn),对元素的一半进行二分搜索。
空间复杂度:O(1)
4、第一个出错的版本
278. 第一个错误的版本(Easy)
# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version): class Solution(object): def firstBadVersion(self, n): left, right = 1, n while left < right: mid = (left + right)//2 if isBadVersion(mid): right = mid else: left = mid + 1 return left
5、旋转数组最小值
153. 寻找旋转排序数组中的最小值(Medium)
旋转之后,右侧的数据一定小于左侧的数据,如果 nums[mid]>nums[right],则最小值在 mid 右侧,新的区间更新为 [mid+1,right], nums[mid]<nums[right],则最小值在 mid 及 mid 左侧,区间更新为 [left,mid]
class Solution(object): def findMin(self, nums): left, right = 0, len(nums)-1 while left < right: mid = (left + right)//2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]
6、目标数在排序数组中出现的首尾位置
34. 在排序数组中查找元素的第一个和最后一个位置(Medium)
先找第一个大于等于 target 的元素下标,再找第一个大于等于 target+1 的元素下标
class Solution(object): def searchRange(self, nums, target): def insert_index(nums, x): left, right = 0, len(nums) while left < right: mid = (left + right) // 2 if nums[mid] < x: left = mid + 1 else: right = mid return left if not nums or target > nums[-1]: return [-1, -1] low = insert_index(nums, target) if target != nums[low]: return [-1, -1] high = insert_index(nums, target + 1) - 1 return [low, high]
这篇关于Leetcode题解-算法-二分法(python版)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python