Codility每周一课：L6 Sorting(P6.4)

0.png

P6.4 NumberOfDiscIntersections

Compute the number of intersections in a sequence of discs.

• P6.4 相交的个数
  计算相交圆盘的个数

在飞机上画N个圆盘。盘片编号从0到N−1。一个由N个非负整数组成的数组A，其元素为盘片的半径。第J个圆盘是以（J，0）为圆心，A[J]为半径绘制的。

如果J-th和K-th圆盘至少有一个公共点（假设圆盘包含其边界），并且J!=K，则称J-th圆盘与K-th圆盘相交。

下图显示了N=6，数组为Ａ时绘制的圆盘，其中：A[0]=1，A[1]=5，A[2]=2，A[3]=1，A[4]=4，A[5]=0

image

上图显示共有11对圆盘相交（其中圆盘Ａ和Ｂ相交，和圆盘Ｂ和Ａ相交看作一个），即：

1. 圆盘1和4相交，并且都与所有其他圆盘相交；
2. 圆盘2也与圆盘0、圆盘3相交。

编写函数：

def solution(A)

给定由N个元素组成的数组A，则返回圆盘相交的个数。如果相交的数目超过10000000，则函数应返回−1。例如给定上面所示的数组A，函数应该返回11。

假定：

1. N是区间[0，100000]内的整数；
2. 数组A的每个元素都是区间[0，2147483647]内的整数；

• 解题思路

对于第i，j个圆盘而言，如果两个圆盘相交的话，则有

image

利用这种方法参见程序solution_direct。其复杂度为O(N**2)。

当然，我们可以把圆盘看作线段，也就是得到每个圆盘的左右范围，然后再判断是否与其他圆盘相交。相交的情况可以分为2种，见程序solution_set，其复杂度为O(N**2)。

因为肯定要遍历数组A，也就是说程序的复杂度为O(N*X)，现在的问题就是减小O(X)。

现在换种思路，见下面的公式：

image

也就是将原来的二维的线段列表变为2个一维的列表。首先遍历数组A得到A[i]+i组成的数组i_limit，以及j-A[j]组成的数组j_limit。然后再遍历数组i_limit中的元素S，利用二分查找算法得到数组j_limit中不大于S的元素个数。前一个操作时间复杂度是O(N)，二分查找算法时间复杂度是O(LogN)，因此最终的时间复杂度为O(N*logN)。程序参见solution。

• python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 6：Sorting
# P 5.3 NumberOfDiscIntersections


def solution_set(A):
    """
    返回数组A代表的圆盘中，相交圆盘的个数,时间复杂度O(N**2)
    :param A: 数组
    :return: 相交圆盘的个数
    """
    limit = []
    length = len(A)
    for index, value in enumerate(A):
        limit.append([max(0, index-value), min(length, index+value)])
    count = 0
    for index, value in enumerate(limit[: -1]):
        for j in limit[index:]:
            if value[0] <= j[0] <= value[1] or j[0] <= value[0] <=j[1]:
                count += 1
    return count


def solution_direct(A):
    """
    返回数组A代表的圆盘中，相交圆盘的个数，时间复杂度O(N**2)
    :param A: 数组
    :return: 相交圆盘的个数
    """
    count = 0
    for index_i, value_i in enumerate(A[:-1]):
        for index_j, value_j in enumerate(A[index_i+1:]):
            if value_i + value_j >= index_j + index_i + 1 - index_i:
                count += 1
    return count


def binary_search(ex_list, ex_num):
    """
    实现二分查找算法，获得ex_num不小于数组ex_list中的元素的个数。适用于ex_num不存在于ex_list中的情况
    :param ex_list: 数组
    :param ex_num: 数值
    :return: 元素的个数
    """
    start = 0
    end = len(ex_list) - 1
    if ex_num <= ex_list[0]:
        return start + 1
    elif ex_num >= ex_list[-1]:
        return end + 1
    else:
        while 1:
            center = (start + end) // 2
            if ex_list[center] > ex_num:
                end = center - 1
            elif ex_list[center + 1] < ex_num:
                start = center + 2
            else:
                return center + 1


def solution(A):
    """
    返回数组A代表的圆盘中，相交圆盘的个数，时间复杂度O(N*log(N)) or O(N)
    :param A: 数组
    :return: 相交圆盘的个数
    """
    count = 0
    i_limit = []
    j_limit = []
    for index, value in enumerate(A):
        i_limit.append(value + index)
        j_limit.append(index - value)
    #  针对i_limit中的每个元素，利用二分查找算法，找到其不小于j_limit中元素的个数
    j_limit.sort()  # 二分法要求数组是有序的
    for ind, val in enumerate(i_limit[:-1]):
        count += max(binary_search(j_limit, val+0.1) - 1 - ind, 0)   
        # 因为i=j时，A[i]+i 肯定不小于j-A[j],也就是说多算了一个，因此要减去1。
        # val之所以加上0.1，因为数组j_limit中都是整数，并且有的整数有多个，这么设置是为了得到最后一个val出现的位置。
        # 减去ind是因为圆盘A和圆盘B相交，次数加上1了，圆盘B和圆盘A相交就不用再加1了。
        if count > 10000000:
            return -1
    return count

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image