本文共 2352 字，大约阅读时间需要 7 分钟。

• ：返回目标字母target插入到有序字母列表letters后下一个字母，如果target无下一个字母，则返回letters[0]，Easy

二分插入

index = bisect.bisect(letters, target)

return letters[index % len(letters)]

class Solution(object):    def nextGreatestLetter(self, letters, target):        """        :type letters: List[str]        :type target: str        :rtype: str        """        start = 0        end = len(letters)-1        while(start<=end):            mid = (start+end)/2            if letters[mid]

• ：给定整数数组nums表示x轴上的点，求两点间第k小距离的值，Hard

二分枚举答案（Binary Search）

利用字典cnt统计各点坐标及其出现次数

排序后将坐标保存在数组keys中，vals中保存对应出现次数的累计值

距离最小值lo可以通过遍历keys得出，距离最大值hi为keys[-1] - keys[0]

在lo ~ hi之间二分枚举距离mi，利用O(n)的遍历统计距离不大于mi的点对个数

import collectionsimport bisectclass Solution(object):    def smallestDistancePair(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: int        """        cnt = collections.Counter(nums)        keys, vals = [], []        for key in sorted(cnt):            keys.append(key)            vals.append(cnt[key] + (vals and vals[-1] or 0))        def countNums(val):            idx = bisect.bisect_right(keys, val)            if idx: return vals[idx - 1]            return 0        def smallerThan(val):            ans = 0            for i, key in enumerate(keys):                ans += (countNums(key + val) - vals[i]) * cnt[key] + cnt[key] * (cnt[key] - 1) / 2            return ans        lo = min(keys[x + 1] - keys[x] for x in range(len(keys) - 1)) if max(cnt.values()) == 1 else 0        hi = keys[-1] - keys[0]        while lo <= hi:            mi = (lo + hi) / 2            if smallerThan(mi) >= k: hi = mi - 1            else: lo = mi + 1        return lo

• ：求乘法表中的第K大数，Hard

答案来源于

首先如果一个数，出现在（X1,Y1），那么它也会出现在(Y1,X1)的位置上

count(t) 用来存储乘法表中不大于t的数字的个数；

以数字4为例子，当x=1时，第一列出现四个数，x=2时，第二列出现2个数，x=3 出现1个数，x =4 出现1个数。再加上m,n的限制

class Solution(object):    def findKthNumber(self, m, n, k):        """        :type m: int        :type n: int        :type k: int        :rtype: int        """        '''        (1,1)        (1,2) (2,1)        (1,3)       (3,1)         (1,4) (2,2)       (4,1)        '''        count = lambda t: sum(min(m, t / x) for x in range(1, n + 1))        lo, hi = 1, k        while lo <= hi:            mid = (lo + hi) / 2            if (count(mid)) >= k:                hi = mid - 1            else:                lo = mid + 1        return lo

转载地址：http://cbqmi.baihongyu.com/