iT邦幫忙

0

【leetcode練功坊】python廣義的二分搜索法概念

二分搜索法,是一個簡單實用的觀念,
在leetcode上可以解掉一大票問題,
一般熟知的二分搜索法可以在排序陣列裡找元素,
但廣義來說,
二分搜索法可以搜索第一個滿足條件的成員

我嘗試將廣義的二分搜索法概念寫出,
達到舉一反三的練習效果

補充說明一下,
我在【python內建模組- bisect】數組二分查找算法一文中有提到python有內建模組 bisect可以解二分搜索問題,
但反正二分搜索的程式碼也不是很長,
懂一下也沒什麼壞處,
修改起來也比較靈活一些

python 二分搜索絕招

二分搜索法的程式型式如下:

def binary_search(array) -> int:
    left, right = 0, len(array)
    while left < right:
        mid = left + (right - left) // 2
        if mid 滿足某條件:
            right = mid
        else:
            left = mid + 1
    return left

運用情境:
在陣列中有個元素,
在此元素左邊均不滿足條件,
在此元素右邊均滿足條件,
找第一個滿足條件的index

參數說明:
left, right設定答案的範圍可能落在區間[left, right)中,
當程式跳出while迴圈時,
left會是第一個滿足條件的值

有了這個模式,對於二分搜索的問題你只需要設定三個部分:

  1. left, right的範圍,需涵蓋可能的答案
  2. 視需求而定決定要回傳「left」還是「left-1」(left-1是最後一個不滿足條件的值)
  3. 決定「某條件」是什麼,這部分最傷腦筋

這邊要補充一下,相信很多人會覺得為什麼取中間值不直觀的寫mid = (left + right)//2就好?
我想可能的原因是其它程式語言有「溢位」的問題,
故習慣上寫mid = left + (right - left) // 2

這樣講還是很抽象,
我們多看幾個例子幫助理解,
看看如何改這個二分搜索絕招幫助解題。

本文收錄題號: 278,35,153,875,1283,1095,275,410,1011,668,719共11題,
相信看完之後對二分搜索會蠻有概念的

練功囉

題目: 278. First Bad Version
題意: 想像你是程式管理者,總共有n個版本的程式,從某一個版本開始出現bug了,你要把第一個出現bug的版本找出來。題目給你函數bool isBadVersion(version)呼叫,用來判斷某個版本是否有bug。

例子:

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. 

解析: 很單純的一道題,既然題目給你isBadVersion函數,就直接代入條件即可

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

題目:35. Search Insert Position
題意: 在一個排序過的陣列要插入一個新的數字,求插入的index?
例子:

Input: [1,3,5,6], 0
Output: 0

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

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

Input: [1,3,5,6], 7
Output: 4

解析: 這一題還算直覺,就是找第一個大於或等於目標的數字

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

題目: 153. Find Minimum in Rotated Sorted Array
題意: 在一個「旋轉」過的排序陣列(例: [0,1,2,4,5,6,7] 可能變 [4,5,6,7,0,1,2])找最小值。假設數字全相異。

解析: 本題找第一個大於或等於陣列尾巴的數字就可以了。以[4,5,6,7,0,1,2]為例,你可以觀察到在切口「0」的地方,左邊[4,5,6,7]都不滿足條件,右邊[0,1,2]都滿足條件,適用二分搜索法。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= nums[-1]:
                right = mid
            else:
                left = mid + 1
        return nums[left]

註: python的內建函數實在太好用,我試過直接寫一行return min(nums)竟也會過關。

這邊要注意陣列的數字全相異是關鍵,如果可能有重複的數字(例如[2,1,2,2]),
那上述方法就不能用(陣列index 0 的2會滿足條件)
如果可能有重複的數字,只能用O(n)的時間找最小值。(參考: 154. Find Minimum in Rotated Sorted Array II)

題目: 875. Koko Eating Bananas
(類似題: 1283. Find the Smallest Divisor Given a Threshold)
題意: Koko愛吃香蕉。現在總共有N堆香蕉,Koko可以決定每個小時要吃k根香蕉,但是同一個小時只能從同一堆裡面拿香蕉。限定時間H小時(保證H>=N,如果HN小,由於同一個小時只能從同一堆裡面拿香蕉,那一定吃不完)求最小的k使得Koko能夠把香蕉吃完。

解析: 如果把k固定,我們可以計算出把香蕉吃完要幾個小時,用此判斷k是否滿足條件。
比如說有三堆香蕉[10, 5, 6],每小時吃四根香蕉,
那總共就需要10/4 + 5/4 + 6/4 = 3+2+2 = 7個小時吃完(除法向上取整)

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        left, right = 1, max(piles)
        while left < right:
            mid = left + (right - left) // 2
            if sum([ceil(p/mid) for p in piles])<=H:
                right = mid
            else:
                left = mid + 1
        return left

題目: 1095. Find in Mountain Array
題意: 在 mountain array裡面找指定的數字(mountain array的定義請點進去看題目,簡單來說就是左邊遞增、右邊遞減的陣增)

解析: 我覺得觀念不難,但可能難在不知道怎麼用他給的API。
這題用到多次二分搜索,
先搜索山峰的位置,再各自對左、右兩邊的陣列做二分搜索

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findPeak(self)-> int:
        left, right = 1, self.length-1
        while left < right:
            mid = left + (right - left) // 2
            if self.get(mid-1)>self.get(mid)>self.get(mid+1):
                right = mid
            else:
                left = mid + 1
        return left-1
    
    def search_inc(self, target, left, right):
        while left < right:
            mid = left + (right - left) // 2
            if self.get(mid)>=target:
                right = mid
            else:
                left = mid + 1
        return left if left<self.length and self.get(left)==target else -1
    
    def search_desc(self, target, left, right):
        while left < right:
            mid = left + (right - left) // 2
            if self.get(mid)<=target:
                right = mid
            else:
                left = mid + 1
        return left if left<self.length and self.get(left)==target else -1
    
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        self.length = mountain_arr.length()
        self.get = mountain_arr.get # 名稱太長,取個別名
        peak = self.findPeak() # 山峰的index
        left_search = self.search_inc(target,0,peak)
        if left_search!=-1:
            return left_search
        return self.search_desc(target,peak, self.length)

挑戰題(可能很難想到這也能用二分搜索)

題目: 275. H-Index II
題意: 若你看原本的題目敘述可能不好理解,其實就是一個整數陣列,找最大整數h使得陣列中h個數大於等於h,這個整數h定義為它的h-index。
題目給你一個排序過的陣列,求h-index。
例子:

Input: [0,1,3,5,6]
Output: 3 
說明: 有三個數字大於或等於3 (3,5,6),但是沒有四個數字大於或等於4 

解析: 我覺得這題難在要花時間理解題意,另外是這題的思維跟其它題目似乎上反向的。
因為其它題目都是找最小滿足條件的數,本題找最大滿足條件的數,需要反向思考才能套用現在的解題模版。
我思考的是index,若index上的數字大於等於此index後面的個數稱為滿足條件。真正的答案是「陣列長度-index」。
這樣講太抽象了,舉個例子:

假設有個陣列長度是95(index為0~94),
如果想檢查index 26有沒有滿足條件,
index 26後面有「95-26=69」個數字,
如果index 26上面的數字在69以上,由於陣列排序過,
就表示有69個數字大於等於69

程式實作:

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        left, right = 0, len(citations)
        while left < right:
            mid = left + (right - left) // 2
            if citations[mid] >= len(citations)-mid:
                right = mid
            else:
                left = mid + 1
        return len(citations)-left

題目: 410. Split Array Largest Sum
(類似題: 1011. Capacity To Ship Packages Within D Days)
考慮答案最小、最大的可能值:

  • m = 1,子陣列就是原來的陣列,答案就是sum(nums)
  • m = len(nums),每個子陣列僅一個元素,答案就是max(nums)

當m介於兩者之間時,答案也一定在兩者的中間

對答案做二分搜索,首先寫一個函數叫做can_split(nums, m, ubd)
判斷「是否有辦法將nums切成m塊子陣列,每塊的最大值不超過ubd」,
如果做的到,表示子陣列的總和的最大值有可能再小一點;
做不到的話,表示答案應該要再大一點

class Solution:
    #函數意義: 是否有辦法將nums切成m塊子陣列,每塊的最大值不超過ubd
    def can_split(self, nums, m, ubd):
        part, curSum = 1, 0
        for num in nums:
            curSum += num
            if curSum > ubd:
                curSum = num
                part+=1
                if part > m:
                    return False;
        return True

    def splitArray(self, nums: List[int], m: int) -> int:
        left, right = max(nums), sum(nums)
        while left < right:
            mid = left + (right - left) // 2
            if self.can_split(nums, m, mid):
                right = mid
            else:
                left = mid + 1
        return left

題意: 給你一個陣列nums,要求切成m個連續子陣列,
要求讓m個子陣列的總和的最大值愈小愈好

譬如:

Input: nums = [1,2,3,4,5,6,7,8,9,10], m = 5
Output: 15
說明: 最好的切割方法是
[1,2,3,4,5], [6,7], [8], [9], [10],
子陣列總和最大值是 1+2+3+4+5=15

題目: 668. Kth Smallest Number in Multiplication Table
題意: 大家都知道「九九乘法表」吧?但是今天的乘法表可能是m*n大小的,給定m, n,求乘法表第k小的數字。
例子:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

其實看到這道題的時候,好像不會想到可以用二分搜索,
我第一個想到的是用「heap」,
因為跟我寫過的資結經典題目: 用heap找前k個最小的數對這道題很像,
但是題目說m, n的大小最大可以到30000,
k也可能很大,
有可能最差的情況就是把mn個元素都拿來排序

這邊二分搜索的想法是找第一個滿足「在乘法表裡面有至少k個數小於或等於自己」的數字,
這樣那個數就會是第k小的數字了

正好要計算乘法表裡面有幾個數小於自己不難,
比如說3*3的乘法表,
看裡面有幾個數字小於5好了

1	2	3
2	4	6
3	6	9

我們一列一列(row)的看,做除法(向下取整):
第一列5/1=5,表示1,2,…,5五個小於5(但是乘法表只有三個數字,取3),
第二列5/2=2,表示2,4兩個數小於5,
第三列5/3=1,表示3一個數小於5

加總min(5,3)+2+1得有六個數小於5

程式:

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        left, right = 1, n * m
        while left < right:
            mid = left + (right - left) // 2
            # 檢查在乘法表裡面是否有至少k個數小於等於num
            if sum(min(mid // v, n) for v in range(1, m + 1))>=k:
                right = mid
            else:
                left = mid + 1
        return left

題目: 719. Find K-th Smallest Pair Distance
題意: 給定一個整數陣列,考慮陣列所有兩兩數對之間的距離,回傳第k小的距離。
例子:

Input:
nums = [1,3,1]
k = 1
Output: 0 
說明:
以下是所有數對的距離:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
最小距離的數對是(1,1),其距離為0

解析: 這一題的思路是找第一個滿足「至少k個數對的距離小於或等於自己」的數字,就跟上一題很像,這一題大概是難在給定一個數字,要怎麼知道有幾個數對的距離小於自己?

如果暴力搜索的話,陣列長度是n就有n*(n-1)/2個數對,時間是O(n^2)。
但是希望可以將時間複雜度改良到O(n)

這裡用了先將陣列排序+two pointer的技巧,
可以欣賞一下程式

class Solution:
    
    # 判斷是否至少有k個數對的距離小於等於distance
    def enough(self, distance, nums, k) -> bool:  # two pointers
        count, i, j = 0, 0, 0
        while i < len(nums) or j < len(nums):
            while j < len(nums) and nums[j] - nums[i] <= distance:  # move fast pointer
                j += 1
            count += j - i - 1  # count pairs
            i += 1  # move slow pointer
        return count >= k
    
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        left, right = 0, nums[-1] - nums[0]
        while left < right:
            mid = left + (right - left) // 2
            if self.enough(mid, nums, k):
                right = mid
            else:
                left = mid + 1
        return left

尚未有邦友留言

立即登入留言