0X00 leetcode 刷題

• LeetCode 378. Kth Smallest Element in a Sorted Matrix
• LeetCode 668. Kth Smallest Number in Multiplication Table
• LeetCode 786. K-th Smallest Prime Fraction
• LeetCode 719. Find K-th Smallest Pair Distance

0X01 基本模板總結(jié)

首先我們有這么一個基本問題

給定一個升序的數(shù)組:

[1, 5, 9, 10, 10, 20]

給定最小值 1 最大值 20 求 第 k 小的元素

hebing

對于第 kth 小的問題,有一種通用解法就是用 k size 的「最大堆」,這個以后再說,今天我們主要用二分查找

二分查找有一個模板:

lo, hi = min, max
while lo < hi:
    mid = lo + (hi - lo) // 2
    if check(xx):
        r = m
    else:
        l = m + 1
 return l

對于這個問題我們的解法如下:

class Solution:
    def kth(self, nums, minNumber, maxNumber, k):
        l, r = minNumber, maxNumber

        # 返回比 n 小于等于的個數(shù)
        def helper(start, end, nums, n):
            if start == end:
                return 1 if n > nums[start] else 0
            if end - start == 1:
                if n >= nums[end]: return 2
                if n >= nums[start]: return 1
                return 0
            if n > nums[end]:
                return end - start + 1
            mid = start + (end - start) // 2
            
            return helper(start, mid, nums, n) + helper(mid+1, end, nums, n)

            return start

        while l < r:
            m = l + (r - l) // 2
            if helper(m) >= k:
                r = m
            else:
                l = m + 1

        return l


a = [1, 4, 5, 5, 5, 5, 5, 5, 8]
s = Solution()
print(s.kth(a, 1, 8, 4))

對于這一種解法,一直有一個這么樣的疑問

為什么二分搜索出來的值,一定在數(shù)組里面..

1. 一定存在第 k 小的值,而且是唯一的
2. 一定是 r 先找到最后的答案
3. r 找到答案后就不會改變了, 直到 l 與 r 合并

0X02 leetcode 做題

378. Kth Smallest Element in a Sorted Matrix

不是最優(yōu)解..但是就是按照上面的模板改的...

如果有重復(fù)元素的話,我就還是用遞歸吧.迭代太復(fù)雜了

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        lo, hi = matrix[0][0], matrix[-1][-1]

        def helper(start, end, nums, n):
            if start == end:
                return 1 if n >= nums[start] else 0
            if end - start == 1:
                if n >= nums[end]: return 2
                if n >= nums[start]: return 1
                return 0
            if n >= nums[end]:
                return end - start + 1
            mid = start + (end - start) // 2
            return helper(start, mid, nums, n) + helper(mid+1, end, nums, n)


        while lo < hi:
            mid = lo + (hi - lo) // 2
            s = 0
            for row in matrix:
                s += helper(0, len(row) - 1, row, mid)
            if s  >= k:
                hi = mid
            else:
                lo = mid + 1
        
        return lo

668. Kth Smallest Number in Multiplication Table

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int: 
        
        # 返回有多少個 <= x 的數(shù)
        def helper(m, n, k, x):
            count = 0
            # 只需要把每一行的 x // i 加起來就行了
            # 如果 i 大于 x  x // i == 0 也就不需要繼續(xù)算下去了
            # 如果 m < x 那么剩下的也不用算了
            # 所以最大值是 min(x, m)
            for i in range(1, min(m+1, x+1)):
                # 一行長度可能不夠
                count += min(x // i, n)
                # 剪枝
                if count >= k: return count
            return count
        
        l, r = 1, m * n + 1

        while l < r:
            mid = l + (r - l) // 2
            if helper(m,n, k, mid) >= k:
                r = mid
            else:
                l = mid + 1

        return l

這道題用了模板題的結(jié)論,

在有重復(fù)的升序列數(shù)組中找到

下面兩道題待做

786. K-th Smallest Prime Fraction

719. Find K-th Smallest Pair Distance