Grind75第8天 | 278.第一个错误的版本、33.搜索旋转排序数组、981.基于时间的键值存储

278.第一个错误的版本

题目链接：https://leetcode.com/problems/first-bad-version

解法：

二分查找。

如果一个版本为错误版本（isBadVersion为True），那么第一个错误版本在该版本左侧（包括该版本）；如果一个版本为正确版本，那么第一个错误版本在该版本的右侧（不包括该版本）。

如此不断收缩范围，直到left和right指针相等。

边界条件：无

时间复杂度：O(logn)

空间复杂度：O(1)

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left ) // 2
            if isBadVersion(mid):
                # 错误版本在 [left, mid] 这个闭区间
                right = mid
            else:
                left = mid + 1
        return left

33.搜索旋转排序数组

题目链接：https://leetcode.com/problems/search-in-rotated-sorted-array

解法：

二分查找，统一写左闭右闭区间：while循环时，left?<=?right。

这个题，麻烦还是在于条件判断时，要不要加 == 符号，比如有时候是 <=，有时候又是 < ，非常容易搞错。我暂时也没想到好的办法。

nums[mid] >= nums[left] 这个条件里加了等号，比如 [3,1]，查找1，这个例子可以验证必须加等号。

以下是官方题解的图：

其他的参考题解。

参考题解：二分查找

边界条件：

时间复杂度：O(logn)

空间复杂度：O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            # 注意这里有等号
            if nums[mid] >= nums[left]:
                # 正因为target不等于nums[mid]，所以需要mid左移一位
                if target >= nums[left] and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # 正因为target > nums[mid] 而不是相等，所以mid肯定不是target的位置，而是右移一位，于是left = mid + 1
                if target > nums[mid] and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

981.基于时间的键值存储

题目链接：https://leetcode.com/problems/time-based-key-value-store

解法：

这个题用二分查找。

看了半天题解也没看明白，无语了，再研究一下。

边界条件：

时间复杂度：O(logn)

空间复杂度：O(n)

class TimeMap:

    def __init__(self):
        self.hashMap = {} # 字典 哈希表，保存<key,[列表]>

    def set(self, key: str, value: str, timestamp: int) -> None:
        curTuple = (value,timestamp)
        if key in self.hashMap: # 之前已经有key和对应列表
            self.hashMap[key].append(curTuple) # 直接在原有列表后面追加一个元组(value,timestamp)
        else: # 之前没有key和对应列表
            curList = [curTuple] # 创建列表
            self.hashMap[key] = curList

    def get(self, key: str, timestamp: int) -> str:
        def lower_bound(nums,x): # 二分查找子函数，返回第一个>=x的下标
            l, r = 0, len(nums)-1
            while l <= r: # 闭区间二分查找，循环结束标志: 区间为空
                mid = (l + r) // 2
                if nums[mid][1] >= x:
                    r = mid - 1 # 循环不变量：r+1以及右边都是 >=x的
                else:
                    l = mid + 1 # 循环不变量: l-1以及左边都是 < x的
            # 循环结束：...,r,l,....
            return l # 返回r+1也可以
        
        if key in self.hashMap:
            index = lower_bound(self.hashMap[key],timestamp+1) - 1 # index是 timestamp+1 第一次出现的位置，那么index-1就是<=timestamp最后一次出现的位置下标
            if index >= 0:
                return self.hashMap[key][index][0]
        return "" # 之前key没出现过 <=timetamp 的时间