面试算法编程选记2题之二分法-寻找斜率为K的2点

2020-06-22T00:00:00+08:00

因为一直是用自学+坚持自学方法走过来的，折腾技术运用还可以，基础算法编程能力一直偏弱。

1、二分法属于思维简单，细节弄人的典型。之前陷入过二分法脑风暴中不能通透，这次趁面试遇到好好再过一次，提高深度。

2、输入数组A 例如 [(x1,y1),(x2,y2)…]，输出斜率为K的点对数目

二分查找¶

二分查找要处理好中点，缩小方法，避免死循环。重在细节实现。 Plus增强后支持最左最右查找

已过 leetcode算法题：https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9

class BinarySearch:
    def getPos(self, A, n, val):
        a1, a2 = 0, n-1 # a1 = 0; a2 = n-1;
        while a1 <= a2:              # a1, a2 位置未检
            mid = (a1+a2)//2        # 中间索引赋值是关键，可等左，不等右
            # print(val, A, a1, a2, mid)
            if A[mid] == val:
                return mid
            elif A[mid] < val:
                # print(A, a1, a2, mid)
                a1 = mid + 1
                # print(A, a1, a2, mid)
            else:
                a2 = mid - 1
        else:
            return -1

    def getPosPlus(self, A, n, val, searchtype=0):
        '''支持最左，最右二分查找的修改Plus版本
        'left':-1, 'fast':0, 'right':1 其中0是默认版本，找到即返回。
        '''
        a1, a2 = 0, n-1
        while a1 < a2:              # 直到重合时，单元素
            mid = (a1+a2)//2        # 中间索引赋值是关键，可等左，不等右
            # print(val, A, a1, a2, mid)
            if A[mid] == val:
                if searchtype == 0:
                    return mid
                if searchtype == -1:
                    a2 = mid
                elif searchtype == 1:
                    a1 = mid
            elif A[mid] < val:
                # print(A, a1, a2, mid)
                a1 = mid
                if a1 + 1 == a2:   #  避免剩余2个元素时， mid=左陷入死循环
                    a1 = a2
                # print(A, a1, a2, mid)
            else:
                a2 = mid
        else:
            assert a1 == a2
            return a1 if A[a1] == val else -1


if __name__ == '__main__':
    rt = BinarySearch()
    for A in ((1,), (1,5), (1, 5, 9), (1, 1, 5), [4,4,10,21]):
        n = len(A)
        for val in A:
            # idx = rt.getPos(A, n, val)
            # print('find %3s in %10s: index=%s' % (val, A, idx))

            # 支持最左，最右二分查找的修改Plus版本
            idx = rt.getPosPlus(A, n, val)
            print('find %3s in %10s: index=%s' % (val, A, idx))
            idx = rt.getPosPlus(A, n, val, -1)
            print('find %3s in %10s: index=%s' % (val, A, idx))

寻找斜率为K的点对¶

算法题：

有一个数组,数组每个元素是一个对象,每个对象有x和y两个值,这个数组记录为A: A = [{x1, y1}, {x2, y2}, …];我们把数组A中任意两个满足以下关系的元素叫做“点对”:(y2-y1)/(x2-x1) = K, K是一个常数。编写程序:给定A与K,返回A中点对的数目。

from itertools import groupby

K = 1 # 斜率

def kpairs(A, k=K):
    '''
    分析：计算一遍点到直线y=kx距离 |Kx - y| / √(k*k+1)，距离等两点的可能与y=kx平行。先验证y=kx上的，距离等不一定平行。
    技巧：结合题目实际，可不开平方pow运算，不取绝对值。
    '''
    print('debug: kpairs(%s, %s)' % (k, A))
    result = 0
    distance = [ (k*x-y) / (k**2+1) for (x, y) in A ]
    point_distance = sorted(zip(A, distance), key=lambda x: x[1])  # 距离排序，取点

    for distance, pointiter in groupby(point_distance, key=lambda x: x[1]):
        points = list(x[0] for x in pointiter)
        count = len(points)
        print('debug: line:y=%3sx, got %3s point distance=%7.3s: %s' % (k, count, distance, points)) # debug
        if count > 1:
            result += count*(count-1)/2 # 组合数 4 -> 6

    return result

if __name__ == '__main__':
    A = [(0,3), (3,0), (3,3), (0,0)]  # 正方形
    assert kpairs(A) == 1, 'check and debug kpairs(%s)'%A
    assert kpairs(A, 10) == 0, 'check and debug kpairs(%s)'%A

    A = [(3,9), (9,9), (20,20), (10,16), (22,28)]
    assert kpairs(A) == 4, 'check and debug kpairs(%s)'%A
    assert kpairs(A, 4) == 1, 'check and debug kpairs(%s)'%A

参考¶

点到直线距离公式的几种推导 https://zhuanlan.zhihu.com/p/26307123

Linux迷+Python粉 - 二分查找法

面试算法编程选记2题之二分法-寻找斜率为K的2点

二分查找¶

寻找斜率为K的点对¶

参考¶