DSA-binary search

算法

一般来说二分都可以用复杂度偏高的做法简单地实现, 比如O(n)的遍历; 但是如何把n变成logn其实很锻炼思维, 所以也记录一下.

4. Median of Two Sorted Arrays

两个排序好的列表,求两个列表合并后的中位数.

1
2
3
4
5
6
7
8
9
Example 1:
    Input: nums1 = [1,3], nums2 = [2]
    Output: 2.00000
    Explanation: merged array = [1,2,3] and median is 2.

Example 2:
    Input: nums1 = [1,2], nums2 = [3,4]
    Output: 2.50000
    Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
  1. 需要注意中位数永远可以用 (nums[(n-1)//2] + nums[n//2]) / 2 表示
  2. L1和R2不交叉或者L2与R1不交叉的情况下我们缩区间
  3. 交叉的时候我们返回L的最大值和R的最小值的均值
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
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1 = len(nums1)
        n2 = len(nums2)

        # mid1一开始是末尾, 如果n2 < n1可能会溢出,得额外处理
        # 举例: [1,2,6,7,8,9,10], [3,4]
        if n2 < n1:
            return self.findMedianSortedArrays(nums2, nums1)

        l = 0
        r = n1 * 2
        MIN = float('-inf')
        MAX = float('inf')
        while l <= r:
            mid1 = l + (r-l) // 2
            mid2 = n1 + n2 - mid1

            L1 = nums1[(mid1-1)//2] if mid1 > 0 else MIN
            R1 = nums1[mid1//2] if mid1//2 < n1 else MAX

            L2 = nums2[(mid2-1)//2] if mid2 > 0 else MIN
            R2 = nums2[mid2//2] if mid2//2 < n2 else MAX

            if L1 > R2:
                r = mid1 - 1
            elif L2 > R1:
                l = mid1 + 1
            else:
                return (max(L1,L2) + min(R1,R2)) / 2
        return None

33. Search in Rotated Sorted Array

反转数组找值, 一个sort之后的列表(无重复值)我们切一刀然后后半部分丢到前面: 比如[1,2,3,4,5]我们在2,3中间切, 就会有[3,4,5,1,2].

给出一个target, 要求找出index, 不存在的时候返回-1

1
2
3
4
5
6
7
8
9
10
11
Example 1:
    Input: nums = [4,5,6,7,0,1,2], target = 0
    Output: 4

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

Example 3:
    Input: nums = [1], target = 0
    Output: -1

画图即可

nums[mid] < nums[l] 对应case1, 然后 nums[mid] < target <= nums[r] 对应后半段, 即l = mid + 1, 否则对应前半段, r = mid - 1

同样逻辑对应case2即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r-l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < nums[l]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1

81. Search in Rotated Sorted Array II

同前一题, 区别是元素可以重复.

最直观的做法就是一旦 nums[mid] == nums[l] 我们就 l += 1, 只要保证这俩不同, duplicates就相当于失去了作用, 之前的逻辑就可以直接套用.

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
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r-l) // 2
            if nums[mid] == target:
                return True
            
            if nums[l] == nums[mid]:
                l += 1
                continue
            
            if nums[mid] < nums[l]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
            
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return False

153. Find Minimum in Rotated Sorted Array

反转列表找出最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:
    Input: nums = [3,4,5,1,2]
    Output: 1
    Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
    Input: nums = [4,5,6,7,0,1,2]
    Output: 0
    Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
    Input: nums = [11,13,15,17]
    Output: 11
    Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

面试碰到了, 细分情况没分出来, 其实正确做法是以最后一个元素为坐标来找. 半开半闭返回l即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        l = 0
        r = n - 1
        while l < r:
            mid = l + (r-l) // 2
            # min在右侧
            if nums[mid] > nums[-1]:
                l = mid + 1
            # min在左侧或者直接是mid
            else:
                r = mid
        return nums[l]

154. Find Minimum in Rotated Sorted Array II

同上题, 但是包含重复, 重复项的解决和之前那题一样, 扫到了直接 r -= 1 即可. 下面的代码可以继续合并elif, 不过这样更直观一些.

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

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

找排序列表中一个数的起始和末尾索引, 不存在的时候返回 [-1, -1]

1
2
3
4
5
6
7
8
9
10
11
Example 1:
    Input: nums = [5,7,7,8,8,10], target = 8
    Output: [3,4]

Example 2:
    Input: nums = [5,7,7,8,8,10], target = 6
    Output: [-1,-1]

Example 3:
    Input: nums = [], target = 0
    Output: [-1,-1]

比较经典的二分, 注意找到值的时候仅 nums[mid] < target 才做 l = mid + 1, 否则 r = mid - 1, 这样才能找到左值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def binsearch(self, nums, target):
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r-l) // 2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.binsearch(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = self.binsearch(nums, target+1)
        return [start, end - 1]

69. Sqrt(x)

字面意思, 求开方

二分

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x
        while l <= r:
            mid = l + (r-l) // 2
            if mid*mid > x:
                r = mid - 1
            else:
                l = mid + 1
        return r

牛顿法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def mySqrt(self, x: int) -> int:
        b = x
        while b*b > x:
            # y = y0 + y'(x-x0)
            # -> x0 - x = y0 / y'
            # -> x = x0 - y0 / y'
            # 而y = x^2 - target
            # -> x = x0 - (x0^2 - target) / 2x0
            # -> x = 0.5x0 + target / 2x0
            # -> x = (x0 + target/x0) / 2
            b = (b + x//b) // 2
        return b

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

然后限制条件 nums[i] != nums[i + 1] for all valid i.

1
2
3
4
5
6
7
8
9
Example 1:
    Input: nums = [1,2,3,1]
    Output: 2
    Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:
    Input: nums = [1,2,1,3,5,6,4]
    Output: 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.

老实说我觉得这题用二分真的挺难理解的. 这里的二分主要是维持中间的区间, 发现递增丢左边界, 递减丢右边界, valley优先丢左, peak直接返回. 但是不管怎么说还是挺抽象的.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1
        n = len(nums)
        while l <= r:
            mid = l + (r-l) // 2
            if mid < n - 1 and nums[mid] < nums[mid+1]:
                l = mid + 1
            elif mid > 0 and nums[mid] < nums[mid-1]:
                r = mid - 1
            else:
                return mid

74. Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

  • Each row is sorted in non-decreasing order.
  • The first integer of each row is greater than the last integer of the previous row.

检查某个target是否在矩阵中

标准二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def binsearch(self, nums, target):
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return r

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        first_col = [x[0] for x in matrix]
        target_row = self.binsearch(first_col, target)
        target_col = self.binsearch(matrix[target_row], target)
        return matrix[target_row][target_col] == target

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

行递增且列递增, 但是不保证其他

即存在左下大于右上的情况.

取路径O(m+n)

PYTHON || EXPLAINED ||

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        i = m - 1
        j = 0
        while i >= 0 and j < n:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        return False

二分O(mlogn)

剪支二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def binsearch(self, nums, target):
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r-l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        col = n
        for row in range(m):
            col = self.binsearch(matrix[row][:col], target)
            if col < n and matrix[row][col] == target:
                return True
        return False

1901. Find a Peak Element II

二维数组找出峰值, 依然非常抽象, 我个人感觉这起码应该是个hard. 列找峰值和前面一样, 区别在于对于每一个mid, 我们去找那一行的最大值索引, 然后去做判断.

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
class Solution:
    def maxRow(self, mat, col):
        idx = -1
        v = -1
        for row in range(len(mat)):
            if mat[row][col] > v:
                v = mat[row][col]
                idx = row
        return idx

    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        n = len(mat[0])

        l = 0
        r = n - 1
        while l <= r:
            mid = l + (r-l) // 2
            row = self.maxRow(mat, mid)
            left = mat[row][mid-1] if mid > 0 else -1
            right = mat[row][mid+1] if mid < n - 1 else -1

            if mat[row][mid] < left:
                r = mid - 1
            
            elif mat[row][mid] < right:
                l = mid + 1
            else:
                return [row, mid]

540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

1
2
3
4
5
6
7
Example 1:
    Input: nums = [1,1,2,3,3,4,4,8,8]
    Output: 2

Example 2:
    Input: nums = [3,3,7,7,10,11,11]
    Output: 10

经典二分, 区别在于需要注意奇偶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        l = 0
        r = n - 1
        while l < r:
            mid = l + (r-l) // 2
            odd = (mid - l) % 2
            if odd:
                if nums[mid] == nums[mid-1]:
                    l = mid + 1
                else:
                    r = mid - 1
            else:
                if nums[mid] == nums[mid-1]:
                    r = mid - 2
                elif nums[mid] == nums[mid+1]:
                    l = mid + 2
                else:
                    return nums[mid]
        return nums[l]

2513. Minimize the Maximum of Two Arrays

We have two arrays arr1 and arr2 which are initially empty. You need to add positive integers to them such that they satisfy all the following conditions:

  • arr1 contains uniqueCnt1 distinct positive integers, each of which is not divisible by divisor1.
  • arr2 contains uniqueCnt2 distinct positive integers, each of which is not divisible by divisor2.
  • No integer is present in both arr1 and arr2.

Given divisor1, divisor2, uniqueCnt1, and uniqueCnt2, return the minimum possible maximum integer that can be present in either array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Example 1:
    Input: divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
    Output: 4
    Explanation: 
    We can distribute the first 4 natural numbers into arr1 and arr2.
    arr1 = [1] and arr2 = [2,3,4].
    We can see that both arrays satisfy all the conditions.
    Since the maximum value is 4, we return it.

Example 2:
    Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
    Output: 3
    Explanation: 
    Here arr1 = [1,2], and arr2 = [3] satisfy all conditions.
    Since the maximum value is 3, we return it.

Example 3:
    Input: divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
    Output: 15
    Explanation: 
    Here, the final possible arrays can be arr1 = [1,3,5,7,9,11,13,15], and arr2 = [2,6].
    It can be shown that it is not possible to obtain a lower maximum satisfying all conditions.

除了题目描述以外, 算是个好题, 二分思路, 找上下界, mid满足的时候可能存在更小值满足 r = mid , mid不满足的时候 l += 1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        lcm_ = math.lcm(divisor1, divisor2)
        l = 0
        r = 1 + max(divisor1, divisor2) * (uniqueCnt1 + uniqueCnt2)
        while l < r:
            mid = l + (r-l) // 2
            check = (mid - mid // divisor1)  < uniqueCnt1 or (mid - mid // divisor2)  < uniqueCnt2 or (mid - mid // lcm_)  < uniqueCnt1 + uniqueCnt2
            if check:
                l = mid + 1
            else:
                r = mid
        return l

410. Split Array Largest Sum

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
    Input: nums = [7,2,5,10,8], k = 2
    Output: 18
    Explanation: There are four ways to split nums into two subarrays.
    The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:
    Input: nums = [1,2,3,4,5], k = 2
    Output: 9
    Explanation: There are four ways to split nums into two subarrays.
    The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

有一说一, 想到了就简单, 想不到就真的难. 一开始我用的递归然后TLE. 后来感觉可以dp但是没找到递归关系, 结果最优解是二分.

递归(TLE)

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
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        sum_ = sum(nums)
        def helper(lst, curr_sum, curr_k):
            if curr_k == 1:
                return curr_sum
            if len(lst) <= curr_k:
                return max(lst)
            curr_avg = curr_sum // curr_k
            curr = 0
            prev = None
            for i in range(len(lst)):
                if prev is None:
                    prev = i
                    curr = lst[i]
                    continue
                if curr + lst[i] < curr_avg:
                    curr += lst[i]
                else:
                    break
                prev = i
            smaller = max(curr, helper(lst[prev+1:], curr_sum-curr, curr_k-1))
            if prev == len(lst) - 1:
                larger = smaller
            else:
                larger = max(curr+lst[prev+1], helper(lst[prev+2:], curr_sum-(curr+lst[prev+1]), curr_k-1))
            return min(smaller, larger)
        return helper(nums, sum_, k)

dp(O(n^2*k))

力扣官方题解

递归关系如图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        f = [[10**18] * (m + 1) for _ in range(n + 1)]
        sub = [0]
        for elem in nums:
            sub.append(sub[-1] + elem)
        
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(i, m) + 1):
                for k in range(i):
                    f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]))
        
        return f[n][m]

二分+贪心

思路很简单, 每次选定一个threshold, 一旦我们需要分大于k个组, 则说明threshold低了, 我们的目标大于该值,l=mid+1; 一旦能够k个组以内满足, 则说明threshold取该值或者小于该值,r=mid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def check(target):
            count = 0
            sum_ = 0
            for i in nums:
                if sum_ + i <= target:
                    sum_ += i
                else:
                    count += 1
                    sum_ = i
            return count+1 > k
        l = max(nums)
        r = sum(nums)
        while l < r:
            mid = l + (r-l) // 2
            if check(mid):
                l = mid + 1
            else:
                r = mid
        return r