LeetCode算法题整理（二分法篇）Binary Search

Posted on   |   Updated on | In | | Visitors

二分法在有序数组中查找元素。原题

1
2
3
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
方法一：实现原理。 
1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        mid = (l+r) // 2
        if nums[mid] > target:
            r = mid - 1
        elif nums[mid] < target:
            l = mid + 1
        else:
            return mid
    return -1

方法二：使用标准库。

1
2
3
4
def search(self, nums, target):
    from bisect import bisect_left 
    index = bisect_left(nums, target)
    return index if index < len(nums) and nums[index] == target else -1

35. Search Insert Position

给定一个target，插入到一个有序数组中，假定数组中无重复元素。原题

1
2
Input: [1,3,5,6], 5
Output: 2
方法一：实现原理。 
1
2
3
4
5
6
7
8
9
10
11
def binary_insert(nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        mid = (l+r) // 2
        if nums[mid] > target:
            r = mid - 1
        elif nums[mid] < target:
            l = mid + 1
        else:
            return mid
    return l

方法二：使用标准库。

1
2
3
def searchInsert(self, nums, target):
    from bisect import bisect_left
    return bisect_left(nums, target)

153. Find Minimum in Rotated Sorted Array

通过一个排序数组旋转后的结果，找出最小元素。原题

1
2
Input: [3,4,5,1,2] 
Output: 1

思路：通过二分法不断缩小范围，由于mid是整除，最后l==mid，并且nums[mid] > nums[r]的。

1
2
3
4
5
6
7
8
9
def findMin(self, nums: List[int]) -> int:
    l, r = 0, len(nums)-1
    while l < r:
        mid = (l+r) // 2
        if nums[mid] <= nums[r]:
            r = mid 
        else:
            l = mid + 1
    return nums[l]

34. Find First and Last Position of Element in Sorted Array

有序数组中查找数组，返回数字的索引范围。原题

1
2
3
4
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def searchRange(self, nums, target):

    left_idx = self.search_edge(nums, target, True)
    if left_idx == len(nums) or nums[left_idx] != target:
        return [-1, -1]
    return [left_idx, self.search_edge(nums, target, False)-1]
    
def search_edge(self, nums, target, left):
    l, r = 0, len(nums)
    while l < r:
        mid = (l+r) // 2
        if nums[mid] > target or (left and nums[mid]==target):
            r = mid
        else:
            l = mid + 1
    return l

278. First Bad Version

找出提交版本中的bad version。原题

1
2
3
4
5
6
7
Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.
1
2
3
4
5
6
7
8
9
def firstBadVersion(self, n):
    l, r = 1, n
    while l <= r:
        mid = (l+r) // 2
        if isBadVersion(mid):
            r = mid - 1
        else:
            l = mid + 1
    return l

374. Guess Number Higher or Lower

猜数游戏1~n，每猜一次会告诉你答案是更小还是更大。原题

1
2
3
4
5
6
7
8
def guess(num):
    return
    -1 : My number is lower
     1 : My number is higher
     0 : Congrats! You got it!
     
Input: n = 10, pick = 6
Output: 6
方法一：实现原理。 
1
2
3
4
5
6
7
8
9
10
def guessNumber(self, n):
    l, r = 1, n
    while l <= r:
        mid = (l+r) // 2
        if guess(mid) == -1:
            r = mid - 1
        elif guess(mid) == 1:
            l = mid + 1
        else:
            return mid

方法二：使用标准库。此答案受stefan大神启发。核心思想为将guess返回的结果转为一个数组，然后使用二分法查找。

1
2
3
4
5
6
7
def guessNumber(self, n):
    from bisect import bisect, bisect_left
    class C:
        def __getitem__(self, x):
            return -guess(x)
    # return bisect(C(), -1, 1, n)
    return bisect_left(C(), 0, 1, n)

解析：以n=10, pick=6为例。实际上C class相当于:

1
2
3
4
ary = map(lambda x: -guess(x), range(1, n+1))
ary.insert(0, None)
# ary = [None, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1]
return bisect(ary, -1, 1, n)

而索引又是从1开始，所以这里在前面添加了一个None，实际上将题转为了查找ary的0，问题便迎刃而解。值得注意的是，如果使用了map，会导致空间，时间复杂度增加，而使用class的方法，并没有求出整个的list，所以效率更高。

744. Find Smallest Letter Greater Than Target

找出比目标大的最小字母，没有的返回首字母。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

方法一：二分法实现。

1
2
3
4
5
6
7
8
9
def nextGreatestLetter(self, letters: 'List[str]', target: 'str') -> 'str':
    lo, hi = 0, len(letters)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if letters[mid] > target:
            hi = mid -1
        elif letters[mid] <= target:
            lo = mid + 1
    return letters[lo % len(letters)]
方法二：使用库。 
1
2
3
def nextGreatestLetter(self, letters: 'List[str]', target: 'str') -> 'str':
    index = bisect.bisect(letters, target)
    return letters[index % len(letters)]

852. Peak Index in a Mountain Array

找到数组中的峰值。假设峰值一定存在。原题

1
2
Input: [0,2,1,0]
Output: 1

方法一：Linear Scan. Time: O(N)

1
2
3
4
def peakIndexInMountainArray(self, A: 'List[int]') -> 'int':
    for i in range(1, len(A)-1):
        if A[i] > A[i+1]:
            return i

方法二：one-line.

1
2
def peakIndexInMountainArray(self, A: 'List[int]') -> 'int':
    return A.index(max(A))
方法三：看到Solution才想到二分法。 
1
2
3
4
5
6
7
8
9
def peakIndexInMountainArray(self, A: 'List[int]') -> 'int':
    lo, hi = 0, len(A)-1
    while lo < hi:
        mid = (lo + hi) // 2
        if A[mid] > A[mid+1]:
            hi = mid
        else:
            lo = mid + 1
    return lo
方法四：黄金分割法，应用在单峰函数求极值，速度比二分法要快。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def peakIndexInMountainArray(self, A: 'List[int]') -> 'int':
    
    def gold1(i, j):
        return i + int(round((j-i) * 0.382))
    def gold2(i, j):
        return i + int(round((j-i) * 0.618))
    
    l, r = 0, len(A) - 1
    x1, x2 = gold1(l, r), gold2(l, r)
    while x1 < x2:
        if A[x1] < A[x2]:
            l = x1
            x1 = x2
            x2 = gold1(x1, r)
        else:
            r = x2
            x2 = x1
            x1 = gold2(l, x2)
    return x1

1014. Capacity To Ship Packages Within D Days

n天内轮船运送的最小容量。原题

1
2
3
4
5
6
7
8
9
10
11
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

贴一下竞赛时AC的丑陋写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def shipWithinDays(self, weights: List[int], D: int) -> int:

    def can_ship(capacity, D):
        l = 0
        for _ in range(D):
            each = 0
            for r in range(l, len(weights)):
                if weights[r]+each <= capacity:
                    each += weights[r]
                else:
                    l = r
                    break
            else:
                return True
        return False
    
    lo, hi = max(weights), sum(weights)
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_ship(mid, D):
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

优化。遇见一个诡异的现象，同样的代码用python比python3快了60ms，和3MB的内存。这解法也没涉及两者的区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shipWithinDays(self, weights: List[int], D: int) -> int:
    lo, hi = max(weights), sum(weights)
    while lo <= hi:
        mid, days, cur = (lo + hi) // 2, 1, 0
        for w in weights:
            if cur+w > mid:
                days += 1
                cur = 0
            cur += w
        if days > D:
            lo = mid + 1
        else:
            hi = mid - 1
        # print(lo, mid, hi)
    return lo

875. Koko Eating Bananas

这道题思路和1014一样。不同的是，如果当前堆的香蕉小于吃的速度，那么也不能吃下一堆。原题

1
2
Input: piles = [3,6,7,11], H = 8
Output: 4

方法一：写习惯了Python3，老是想写//，注意是p/mid。

1
2
3
4
5
6
7
8
9
10
11
def minEatingSpeed(self, piles: List[int], H: int) -> int:
    lo, hi = 1, max(piles) 
    while lo <= hi:
        mid = (lo + hi ) >> 1
        # needs = sum(math.ceil(p/mid) for p in piles)   # slower
        needs = sum((p-1)//mid+1 for p in piles)
        if needs > H:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

1145. Binary Tree Coloring Game

二叉树染色游戏。两个人轮流给二叉树染色，每次只能染相邻位的节点，给定第一个人染色的位置，问第二个人是否能够必胜。原题

方法一：关键的一点需要想明白，从第一个人染色的地方，有三个分支，如果有一个分支可以大于整个节点的一半，那么第二个人选择这个分支，就能赢得比赛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
    count = [0, 0]
    
    def dfs(node):
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        if node.val == x:
            count[0] = left
            count[1] = right
        return left + right + 1

    dfs(root)
    return max(max(count), n - sum(count) - 1) > n // 2

33. Search in Rotated Sorted Array

在有序数组旋转后查找目标索引。原题

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

方法一：这个题开始的时候结合两个题，一个是旋转数组中的最小值，然后重组成一个原数组，最后在二分搜索加上原来偏移的索引值。但是这样使用了两次二分法，所以效率不高。看了stefan的答案后明白了，需要找到另一个比较的值就是nums[0]。这里分了两种情况，一种是当nums[0]<=nums[mid]，这种情况说明了nums[:mid]是有序的；另一种是nums[mid]<nums[0]，说明nums[:mid]中存在一个下落点，然后又根据target在下落点的左右分为两种情况。记住条件中target始终有=。其实有一个等号可以去掉，但是为了方便好记。

1
2
3
4
5
6
7
8
9
10
11
12
def search(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo+hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[0]<=target<nums[mid] or nums[mid]<nums[0]<=target or target<=nums[mid]<nums[0]:
            hi = mid - 1
        else:
            lo = mid + 1
            
    return -1

81. Search in Rotated Sorted Array II

同33题，区别在于数组中可能有重复的数字，返回是否存在即可。

1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

方法一：核心代码在于七八行，当左边界和中间相等时，左边界递增。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def search(self, nums: List[int], target: int) -> bool:
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo+hi) >> 1
        if nums[mid] == target:
            return True
        while lo<mid and nums[lo]==nums[mid]:
            lo += 1
        if nums[lo] <= nums[mid]: # 左侧有序
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                     # 右侧有序，因为下落点在左侧
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False

1283. Find the Smallest Divisor Given a Threshold

找到一个除数，用数组所有元素除它得到的天花板数和刚好小于等于阈值。求这个数最小是多少。原题

1
2
3
4
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

方法一：这道题和大佬的解法差不多。区别在于我用了math的库，而他用了一个式子来求的天花板数。知识点(a + b - 1) // b == math.ceil(a/b)

1
2
3
4
5
6
7
8
9
10
11
def smallestDivisor(self, nums: List[int], threshold: int) -> int:

    lo, hi = 1, max(nums)
    while lo <= hi:
        mid = (lo + hi) // 2
        # if sum(math.ceil(i/mid) for i in nums) <= threshold:
        if sum((i+mid-1) // mid for i in nums) <= threshold:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

1268. Search Suggestions System

单词推荐系统。原题

1
2
3
4
5
6
7
8
9
10
11
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

方法一：二分法。此题暴力法求解也能过。更好的方法还是二分或者Trie，但是Trie的方式实现过于复杂。

1
2
3
4
5
6
7
8
def suggestedProducts(self, p: List[str], w: str) -> List[List[str]]:
    p.sort()
    ans, prefix, i = [], '', 0
    for c in w:
        prefix += c
        i = bisect.bisect_left(p, prefix, i)
        ans.append([d for d in p[i:i+3] if d.startswith(prefix)])
    return ans

392. Is Subsequence

判断一个字符串是否是另一个的子序列。原题

1
2
Input: s = "abc", t = "ahbgdc"
Output: true

方法一：生成器。

1
2
3
def isSubsequence(self, s: str, t: str) -> bool:
    t = iter(t)
    return all(c in t for c in s)

方法二：二分法。将每个字符的索引用列表记录下来，每次用二分法找后序出现的匹配的字符。

1
2
3
4
5
6
7
8
9
10
def isSubsequence(self, s: str, t: str) -> bool:
    idx = defaultdict(list)
    for i, c in enumerate(t):
        idx[c].append(i)
    prev = 0
    for i, c in enumerate(s):            
        j = bisect.bisect_left(idx[c], prev)
        if j == len(idx[c]): return False
        prev = idx[c][j] + 1
    return True

1482. Minimum Number of Days to Make m Bouquets

花圃里有若干的花束记录了第几天会开花。最小的天数，可以做出m束花，必须使用连续的花才能做成一朵花束。需要k束花。原题

1
2
3
4
5
6
7
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

方法一：比赛的时候真是一点都没往二分法想、这个是Lee的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minDays(self, A: List[int], m: int, k: int) -> int:
    if m * k > len(A): return -1
    lo, hi = 1, max(A)
    while lo < hi:
        mid = (lo + hi) // 2
        flow = bouq = 0
        for a in A:
            flow = 0 if a > mid else flow + 1
            if flow >= k:
                bouq += 1
                flow = 0
                if bouq == m:
                    break
        if bouq == m:
            hi = mid
        else:
            lo = mid + 1
    return lo

1201. Ugly Number III

找到第n个能被a或b或c整除的数。原题

1
2
3
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

方法一：这题和 丑数2的题不一样，那道题是只能被2，3，5整除的数。这题一开始也是没想到用二分法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
    lo, hi = 1, 2 * 10**9
    ab = a*b // math.gcd(a, b)
    ac = a*c // math.gcd(a, c)
    bc = b*c // math.gcd(b, c)
    abc = a*bc // math.gcd(a, bc)
    while lo <= hi:
        mid = (lo+hi) // 2
        total = mid//a + mid//b + mid//c - mid//ab - mid//ac - mid//bc + mid//abc
        if total >= n:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

287. Find the Duplicate Number

找到重复的数字，在1~n中有一个数至少重复了一次，但是其它数可能没有，找到这个重复的数字。原题

方法一：用过这个方法，但是没想到能用在这道题上，方法是解环形链表中入口节点的那道题。因为数组中存在重复的数字，所以这样延伸下去一定是有环。 
1
2
3
4
5
6
7
8
9
10
11
def findDuplicate(self, nums: List[int]) -> int:
    slow = nums[0]
    fast = nums[slow]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    head = 0
    while head != fast:
        fast = nums[fast]
        head = nums[head]
    return head

方法二：二分法。比较的是数字的多少。

1
2
3
4
5
6
7
8
9
def findDuplicate(self, nums: List[int]) -> int:
    lo, hi = 1, len(nums)-1
    while lo < hi:
        mid = (lo + hi) // 2
        if sum(i<=mid for i in nums) <= mid:
            lo = mid + 1
        else:
            hi = mid
    return lo

154. Find Minimum in Rotated Sorted Array II

旋转数组找到最小值，与1不同的是，这里有重复的值。原题

方法一：由于重复值的原因，[10, 1, 10, 10, 10]，[10, 10, 10, 1, 10] 

1
2
3
4
5
6
7
8
9
10
11
def findMin(self, nums: List[int]) -> int:
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = (lo+hi) >> 1
        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            hi -= 1
    return nums[lo]

1539. Kth Missing Positive Number

找到第k个缺失的正数，数组可能会被耗尽。原题

1
2
3
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

方法一：用了集合。

1
2
3
4
5
6
7
8
def findKthPositive(self, arr: List[int], k: int) -> int:
    s = set(arr)
    for i in range(1, 2002):
        if i not in s:
            k -= 1
        if k == 0:
            return i
    return i
方法二：二分法by@lee215。lo是什么？是最后的结果里面存在了多少数，那么结果就是lo+k。对于数组[2,3,4,7,11] A[m]-1-m表示缺失了几个数。 
1
2
3
4
5
6
7
8
9
def findKthPositive(self, A: List[int], k: int) -> int:
    l, r = 0, len(A)
    while l < r:
        m = (l + r) // 2
        if A[m] - 1 - m < k:
            l = m + 1
        else:
            r = m
    return l + k

1552. Magnetic Force Between Two Balls

在若干的指定的位置可以放置球，问如何使球之间最小的距离最大化。原题

1
2
3
Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

方法一：比赛的时候想了一下二分法，但是没多想。这里只要想明白这个辅助方法就能实现了。count方法表示距离为d时最多可以放几个球。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maxDistance(self, position: List[int], m: int) -> int:
    position.sort()
    n = len(position)
    
    def count(d):
        cnt, cur = 0, float('-inf')
        for p in position:
            if p - cur >= d:
                cnt += 1
                cur = p
        return cnt
    
    lo, hi = 0, position[-1]-position[0]
    while lo <= hi:
        mid = (lo+hi) // 2
        if count(mid) >= m:
            lo = mid + 1
        else:
            hi = mid - 1
    
    return hi

162. Find Peak Element

找到数组中的峰值，数组中元素两个挨着的元素不重复。可能存在多个值，返回任意一个即可。原题

1
2
3
4
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

方法一：因为挨着的元素不重复，所以可以用二分法。比较两个相邻的元素，如果做左小于右说明峰值在右侧。

1
2
3
4
5
6
7
8
9
10
def findPeakElement(self, nums: List[int]) -> int:
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = (lo+hi) // 2
        mid2 = mid + 1
        if nums[mid] < nums[mid2]:
            lo = mid2
        else:
            hi = mid
    return lo

1095. Find in Mountain Array

查找山峰数组中的元素，优先返回左侧的索引，如果都没有返回-1。原题

1
2
3
Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

方法一：三次二分法，想到了这个方式，犹豫了一下，因为觉得这种方式在最坏的情况下取值会超过100次。

第一次找到峰值，和162一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def findInMountainArray(self, target: int, A: 'MountainArray') -> int:
    lo, hi = 0, A.length()-1
    while lo < hi:
        mid = (lo+hi) // 2
        mid2 = mid + 1
        if A.get(mid) < A.get(mid2):
            lo = mid2
        else:
            hi = mid
    peak = lo
    lo, hi = 0, peak
    while lo <= hi:
        mid = (lo+hi) // 2
        mid_val = A.get(mid)
        if mid_val > target:
            hi = mid - 1
        elif mid_val < target:
            lo = mid + 1
        else:
            return mid
            
    lo, hi = peak, A.length()-1
    while lo <= hi:
        mid = (lo+hi) // 2
        mid_val = A.get(mid)
        if mid_val > target:
            lo = mid + 1
        elif mid_val < target:
            hi = mid - 1
        else:
            return mid
    return -1

74. Search a 2D Matrix

在2d数组中搜索目标，把数组抻成一维的也是有序数组。原题

1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

方法一：一开始没想到这个方法，而是先bisect_right找行，然后再在行里二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False
    n = len(matrix[0])
    lo, hi = 0, n*len(matrix)-1
    while lo <= hi:
        mid = (lo+hi) // 2
        if matrix[mid//n][mid%n] > target:
            hi = mid - 1
        elif matrix[mid//n][mid%n] < target:
            lo = mid + 1
        else:
            return True
    return False

436. Find Right Interval

找到每个段的右侧的段的索引，右侧的段意味着起始点大于等于该段结尾点的并且最近的段。原题

1
2
3
4
5
6
7
8
9
Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.
[ [3,4], [6,9], [5,8] ]
[2,-1,-1]

方法一：二分法。理清题意后挺简单的。

1
2
3
4
5
6
7
8
9
def findRightInterval(self, intervals: 'List[Interval]') -> List[int]:
    starts = [(start, i) for i, (start, _) in enumerate(intervals)]
    starts.append((float('inf'), -1))
    starts.sort()
    ans = []
    for _, end in intervals:
        i = bisect.bisect_left(starts, (end, ))
        ans.append(starts[i][-1])
    return ans

方法二：压缩一下。

1
2
3
4
def findRightInterval(self, intervals: 'List[Interval]') -> List[int]:
    starts = [(start, i) for i, (start, _) in enumerate(intervals)] + [(float('inf'), -1)]
    starts.sort()
    return [starts[bisect.bisect_left(starts, (end, ))][-1] for _, end in intervals]

911. Online Election

找到某一时间的选举票最多的人。

1
2
3
4
5
6
7
Input: ["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
Output: [null,0,1,1,0,0,1]
Explanation: 
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

方法一：二分法，挺简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        self.leading = []
        tickets = collections.defaultdict(int)
        max_votes, candidate = 0, 0
        for p, t in zip(persons, times):
            tickets[p] += 1
            if tickets[p] >= max_votes:
                candidate = p
                max_votes = tickets[p]
            self.leading.append((t, candidate))
        
    def q(self, t: int) -> int:
        i = bisect.bisect(self.leading, (t, float('inf')))        
        return self.leading[i-1][1]
方法二：Lee的方法，写法上改进，时间并不需要绑定在一起，可以通过二分时间索引找选举人。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        self.leading = []
        self.times = times
        tickets = collections.defaultdict(int)
        lead = -1
        for p in persons:
            tickets[p] += 1
            if tickets[p] >= tickets[lead]:
                lead = p
            self.leading.append(lead)
        
    def q(self, t: int) -> int:
        i = bisect.bisect(self.times, t)      
        return self.leading[i-1]

378. Kth Smallest Element in a Sorted Matrix

有个二维矩阵行列都是有序的，找到第K个最小的元素。

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

方法一：可以用堆，暴力地解决，效率也很高。不过这样的话，有序的条件相当于没有用上。

1
2
3
4
5
6
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    heap = sum(matrix, [])
    heapq.heapify(heap)
    for _ in range(k):
        ans = heapq.heappop(heap)
    return ans
方法二：不需要全部都塞到堆里。这里注意只有首行元素需要添加右侧的节点到堆中。 
1
2
3
4
5
6
7
8
9
10
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    heap = [(matrix[0][0], 0, 0)]
    N = len(matrix)
    for _ in range(k):
        val, i, j = heapq.heappop(heap)
        if i==0 and j+1<N:
            heapq.heappush(heap, (matrix[i][j+1], i, j+1))
        if i + 1 < N:
            heapq.heappush(heap, (matrix[i+1][j], i+1, j))
    return val
方法三：二分法，找到中间的数和k比较。 
1
2
3
4
5
6
7
8
9
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    lo, hi = matrix[0][0], matrix[-1][-1]
    while lo < hi:
        mid = (lo + hi) // 2
        if sum(bisect.bisect(row, mid) for row in matrix) < k:
            lo = mid + 1
        else:
            hi = mid
    return lo

1157. Online Majority Element In Subarray

实时的最多元素查询。原题

1
2
3
4
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

方法一：竞赛时，用了个dict嵌套，内存溢出了。此题的解法是存索引，然后二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.c = collections.defaultdict(list)
        for i, x in enumerate(arr):
            self.c[x].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        for k, v in self.c.items():
            if len(v) < threshold:
                continue

            low = bisect.bisect_left(v, left)
            high = bisect.bisect_right(v, right)
            if high - low >= threshold:
                return k
        return -1

1146. Snapshot Array

数组的快照。原题

1
2
3
4
5
6
7
8
9
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

方法一：此题暴力法时，空间复杂度会过高。采用针对每个元素，变化时，记录该变化的历史。再用二分法查找。

注意查找时，是通过数组查找而不是数字，查找比其大的再-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class SnapshotArray:

    def __init__(self, length: int):
        self.ary = [[[-1, 0]] for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.ary[index].append([self.snap_id, val])
        

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1
        

    def get(self, index: int, snap_id: int) -> int:
        i = bisect.bisect(self.ary[index], [snap_id+1]) - 1
        return self.ary[index][i][1]

1847. Closest Room

找到满足size的最近id的房间。

1
2
3
4
5
6
Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.

方法一：看数据量很容易能够想到是二分法，但是还需要想到离线算法，这个题要将query顺序打乱。这里是官方的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import sortedcontainers
class Event:
    """
    op: 事件的类型，0 表示房间，1 表示询问
    size: 房间的 size 或者询问的 minSize
    idx: 房间的 roomId 或者询问的 preferred
    origin: 房间在数组 room 中的原始编号或者询问在数组 queries 中的原始编号
    """
    def __init__(self, op: int, size: int, idx: int, origin: int):
        self.op = op
        self.size = size
        self.idx = idx
        self.origin = origin

    """
    自定义比较函数，按照事件的 size 降序排序
    如果 size 相同，优先考虑房间
    """
    def __lt__(self, other: "Event") -> bool:
        return self.size > other.size or (self.size == other.size and self.op < other.op)


class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        N = len(queries)
        res = [-1] * N

        events = []
        for i, (room_id, size) in enumerate(rooms):
            events.append(Event(0, size, room_id, i))
        
        for i, (preferred_id, min_size) in enumerate(queries):
            events.append(Event(1, min_size, preferred_id, i))

        events.sort()

        valid = sortedcontainers.SortedList()

        for event in events:
            if event.op == 0:
                valid.add(event.idx)
            else:
                # 询问事件
                dist = float("inf")
                # 查找最小的大于等于 preferred 的元素
                x = valid.bisect_left(event.idx)
                if x != len(valid):
                    dist = valid[x] - event.idx
                    res[event.origin] = valid[x]
                if x != 0:
                    # 查找最大的严格小于 preferred 的元素
                    x -= 1
                    if event.idx - valid[x] <= dist:
                        dist = event.idx - valid[x]
                        res[event.origin] = valid[x]
        return res

2040. Kth Smallest Product of Two Sorted Arrays

两个有序数组的第k小的乘积。

1
2
3
4
5
6
Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The 2 smallest products are:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
The 2nd smallest product is 8.

方法一：这题需要转换一下思路来二分，以乘积来二分，如果小于等于x的刚好有k个，那么乘积就是x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:

    def check(x):
        # 乘积小于等于x的有多少个
        total = 0
        for n1 in nums1:
            if n1 > 0:
                total += bisect.bisect(nums2, x//n1)
            elif n1 == 0:
                total += (x>=0) * len(nums2)
            else:
                total += len(nums2) - bisect_left(nums2, ceil(x/n1))
        return total

    lo, hi = -10**10-1, 10**10+1
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

792. Number of Matching Subsequences

求words里是s子序列的个数。

1
2
3
Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

方法一：二分法。如果暴力求子序列会超时，这里使用二分法判断是否是子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def numMatchingSubseq(self, s: str, words: List[str]) -> int:

    idx = defaultdict(list)
    for i, c in enumerate(s):
        idx[c].append(i)

    def is_subseq(t, s):
        prev = 0
        for c in t:
            i = bisect.bisect_left(idx[c], prev)
            if i == len(idx[c]): return False
            prev = idx[c][i] + 1
        return True

    return sum(is_subseq(word, s) for word in words)

方法二：这个方法很新颖，分桶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def numMatchingSubseq(self, s: str, words: List[str]) -> int:

    buckets = defaultdict(list)
    for word in words:
        buckets[word[0]].append(word)

    res = 0
    for c in s:
        nxt = buckets[c]
        buckets[c] = []
        for w in nxt:
            suffix = w[1:]
            if not suffix:
                res += 1
            else:
                buckets[suffix[0]].append(suffix)
    return res