时间戳

首页 > 解决方案 > Python-查找给定列表的邻居数量

python - Python-查找给定列表的邻居数量

问题描述

问题陈述 在数轴上有 N 个房子（1 个数字可以有更多房子）。如果两所房子之间的距离小于某个给定的 D，则称两栋房子是邻居。（两栋相同编号的房子之间的距离为 1）求所有邻居的数量。

从数学上讲，问题归结为这一点。给定一个多重集 N 和一个数字 D 找出它们之间的距离小于 D 的房屋数量

def main():
    number_of_ppl,distance=map(int, input().split())
    inputs=map(int,input().split())

    numbers=sorted(inputs)
    counter=0
    sum=0
    for x in range(0,len(numbers)):

        for y in range(i+1,len(numbers)):

                if abs(numbers[x]-numbers[y])<=distance:
                    counter +=1
                else:
                    break
        sum+=counter
        counter=0
    print(sum)

main()

此代码有效，但是由于时间不足，它在 8 个测试用例中的 3 个失败。有什么我想念的吗？我怎样才能使这个算法更快？我尝试使用字典，但得到了相同的结果

PS如果有帮助，我可以发布该程序失败的测试用例

标签： pythonpython-3.xoptimization

解决方案

您当前的代码不完整，但似乎您正在执行 2 个循环，如果距离足够大，则需要 O(n^2) 才能运行。这可以减少到 O(n log n)。请注意，当您按顺序迭代数字时，当您分析 arr[i] 的邻居时，当查看 arr[i + 1] 的邻居时，它们将是相同的 + 可能更多。

    def main():
        number_of_ppl,distance=map(int, input().split())
        inputs=map(int,input().split())
        numbers = sorted(inputs)

        sum = 0
        pointer = 0
        for idx, number in enumerate(numbers):
            while pointer < len(numbers) and number + distance >= numbers[pointer]:
                pointer += 1
            sum += (pointer - idx)
        print(sum)

    main()

推荐阅读