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 NumberOfDiscIntersectionsdef 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 countdef 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 countdef 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 + 1def 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，获取更多。

imageimage