Leetcode刷题-二分查找

灵神的二分视频：二分查找 红蓝染色法_哔哩哔哩_bilibili

34

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:right = len(nums) - 1left = 0res = [-1,-1]mid = int((right + left)/2)while right >= left:if nums[mid] < target:left = mid + 1mid = int((right + left)/2)continueif nums[mid] > target:right = mid - 1mid = int((right + left)/2)continueif nums[mid] == target:res[0] = midres[1] = midbreakif res[0] != -1:right = mid + 1left = mid - 1while right >= 0 and right < len(nums):if nums[right] != target:breakres[1] = rightright += 1while left >= 0:if nums[left] != target:breakres[0] = leftleft -= 1return res

35

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left = -1right = len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] < target:left = midelse:right = midreturn right

704

class Solution:def search(self, nums: List[int], target: int) -> int:left = -1right = len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] < target:left = midelse:right = midif right >= 0 and right < len(nums) and nums[right] == target:return rightelse:return -1        

744

class Solution:def nextGreatestLetter(self, letters: List[str], target: str) -> str:left = -1right = len(letters)while left + 1 < right:mid = (left + right) // 2if letters[mid] < chr(ord(target) + 1):left = midelse:right = midif right >= 0 and right < len(letters):return letters[right]else:return letters[0]

2529

class Solution:def maximumCount(self, nums: List[int]) -> int:left = -1right = len(nums)pos = 0neg = 0while left + 1 < right:mid = (left + right) // 2if nums[mid] < 1:left = midelse:right = midpos = len(nums) - rightleft = -1right = len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] < 0:left = midelse:right = midneg = rightreturn max(pos,neg)

1385

class Solution:def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:arr2.sort()res = 0for taget in arr1:left = -1right = len(arr2)while left + 1 < right:mid = (left + right) // 2if arr2[mid] + d < taget:left = midelse:right = midif right == len(arr2) or arr2[right] > taget + d:res += 1return res    

1385

     先将potions列表排序，保证它是一个单调列表。然后遍历每一个咒语，找到刚好满足success条件的位置，即求出当前咒语和药水的成功对数。

class Solution:def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:potions.sort()res = []for i in spells:left = -1right = len(potions)while left + 1 < right:mid = (left + right) // 2if i * potions[mid] < success:left = midelse:right = midres.append(len(potions)-right)return res

2389

class Solution:def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:ans = []nums.sort()for j in range(1,len(nums)):nums[j] += nums[j-1]print(nums)for i in queries:left = -1right = len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] < i + 1:left = midelse:right = midans.append(right)return ans

1170

使用二分查找找到刚好比queries中统计值大1的位置，再用words的长度减去即为答案。

class Solution:def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:q = []w = []for i in words:a = min(i)w.append(i.count(a,0,len(i)))for j in queries:b = min(j)q.append(j.count(b,0,len(j)))w.sort()res = []for k in q:left = -1right = len(w)while left + 1 < right:mid = (left + right) // 2if w[mid] < k + 1:left = midelse:right = midres.append(len(w) - right)return res

2080

先记录每个数字出现的位置，再用二分查找找出满足的位置，先找左端，再找右端。

class RangeFreqQuery:def __init__(self, arr: List[int]):pos = defaultdict(list)for i, x in enumerate(arr):pos[x].append(i)self.pos = posdef query(self, left: int, right: int, value: int) -> int:a = self.pos[value]# a.sort()lf = -1lr = len(a)while lf + 1 < lr:mid = (lf + lr) // 2if a[mid] < left:lf = midelse:lr = midres = 0res += lrlf = -1lr = len(a)while lf + 1 < lr:mid = (lf + lr) // 2if a[mid] < right + 1:lf = midelse:lr = midres = lr - resreturn res# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)

2563

        排序，然后进行二分查找。排序后顺序可能会混乱，题目要求的是下标 i < j。但是经过分析，我们可以发现，如果使用暴力做法，那么nums[j] 再整个过程中，和除了他自己本身的数都进行了一次数对判断（即nums[j] + 任意非自己的数）。 假设数对（i，j），i < j 满足nums[i] + nums[j] >= lower && nums[i] + nums[j] <= upper,那么数对（j，i）也满足，所以在结果上这两个数组是等价的，但由于题目要求只要（i，j），所以取其中一半即可，也就是我们可以忽略对原数组排序后下标的改变，保证只计入（i，j）或者（j，i）其中一种到答案中即可。所以我们可以设置每一次二分查找的区间为[ 0 , j - 1] （我这里采用的是开区间写法，所以是 [ 0 , j ]），这样就可以保证只计入（i，j）或者（j，i）。

class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:res = 0n = numsn.sort()for i in range(len(n)):x = n[i]left = -1right = iwhile left + 1 < right:mid = (left + right) // 2if n[mid] + x < lower:left = midelse:right = midp1 = rightleft = -1right = iwhile left + 1 < right:mid = (left + right) // 2if n[mid] + x < upper + 1:left = midelse:right = midres += (right - p1)return res

2856

class Solution:def minLengthAfterRemovals(self, nums: List[int]) -> int:x = nums[len(nums) // 2]left = -1right = len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] < x:left = midelse:right = midp1 = rightleft = -1right = len(nums)while left + 1 < right:mid = (left + right) // 2if nums[mid] < x + 1:left = midelse:right = midres = right - p1return max(res * 2 - len(nums), len(nums) % 2)