code

google common

import com.google.common.base.CharMatcher;
/**
 * 去掉SQL表达式的特殊字符.
 * 
 * @param value SQL表达式
 * @return 去掉SQL特殊字符的表达式
 */
public static String getExactlyValue(final String value) {
    return null == value ? null : CharMatcher.anyOf("[]`'\"").removeFrom(value);
}

python's bisect_left

#
# @lc app=leetcode.cn id=719 lang=python3
#
# [719] 找出第 K 小的数对距离
#

# @lc code=start
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def count(mid: int) -> int:
            cnt = i = 0
            for j, num in enumerate(nums):
                while num - nums[i] > mid:
                    i += 1
                cnt += j - i
            return cnt

        nums.sort()
        return bisect_left(range(nums[-1] - nums[0]), k, key=count)

# @lc code=end

test assert hasItems

assertThat(actualSQLs, hasItems(targetSQLs.toArray(new String[0])));

topk_BFPRT.md

""" BFPRT算法，简称 TOP K 问题，用来求数组中第k小元素的算法 - 可以在O（n）时间内求出答案 """ class Solution: def get_median(self, nums): '''计算5个数的中位数''' begin, end = 0, len(nums) - 1

    sum = begin + end
    mid = sum // 2 + sum % 2  # 这个地方加上sum%2是为了确保偶数个数时我们求的是中间两个数的后一个
    return sorted(nums)[mid]  # 常量级别，影响不大，也可改用插入排序

def BFPRT(self, nums, left, right):
    '''选择partition基准: 划分每5个一组，求每组的中位数'''
    num = right-left + 1
    offset = 0 if num % 5 == 0 else 1  # 最后如果剩余的数不足5个，我们也将其分成一个小组，和前面同等对待
    group = num//5 + offset

    median = []  # 中位数数组
    for i in range(group):
        begin = left + i * 5
        end = begin + 4
        Median = self.get_median(nums[begin:min(end, right) + 1])
        median.append(Median)
    return self.get_median(median)  # 这里是求中位数数组的中位数，再调用getmedian不就行了，为啥有的人还要用下面递归select，虽然也是正确的，但直接getmedian快一点啊
    # return select(median, 0, groups-1, groups//2)  # 求出生成好的median数组的中位数，作为partation函数的划分值

def partition(self, nums, left, right, base):
    '''将基准base归位'''
    if left >= right:
        return

    temp = nums[base]
    nums[base], nums[right] = nums[right], nums[base]  # 和尾部节点交换

    max_index = left
    for i in range(left, right):
        if nums[i] < temp:
            nums[max_index], nums[i] = nums[i], nums[max_index]
            max_index += 1
    nums[max_index], nums[right] = nums[right], nums[max_index]
    return max_index

def select(self, nums, left, right, K):
    '''快速选择过程'''
    if left == right:
        return nums[left]

    base = self.BFPRT(nums, left, right)                              # 选择基准
    base_index = self.partition(nums, left, right, nums.index(base))  # 基准归位

    if base_index == K:   # 判断目前已归位的基准，是不是第K位
        return nums[base_index]
    elif base_index > K:  # 递归左半部分
        return self.select(nums, left, base_index - 1, K)
    else:                 # 递归右半部分
        return self.select(nums, base_index + 1, right, K)

def MoreThanHalfNum_Solution(self, numbers):
    if not numbers:
        return 0

    left, right = 0, len(numbers) - 1
    length = len(numbers)
    K = right // 2
    ans = self.select(numbers, left, right, right - K + 1)  # 第K大，也是第N-K+1小

    # 核实
    cnt = 0
    for x in numbers:
        if x == ans:
            cnt += 1
            if cnt == length // 2 + 1:
                return ans
    return 0

数组中出现次数超过一半的数字

s = Solution() ans = s.MoreThanHalfNum_Solution([1, 2, 3, 2, 2, 2, 5, 4, 2])