时间戳

首页 > 解决方案 > 从（位置，范围）元组创建分组字典

dictionary - 从（位置，范围）元组创建分组字典

问题描述

给定（位置，范围）元组列表，我如何返回从给定位置可到达的所有位置的字典。

例如，如果输入列表是 [(0,2),(2,3),(4,1),(8,3)] 我们应该返回一个字典

d[0]=[0,2]
d[2]=[0,2,4]
d[4]=4
d[8]=8

因为，例如，位置 2 处的点的范围为 3，因此可以到达 - 1<x<5 的任何内容，这将覆盖 0,4 处的点及其本身 2。

我使用双 for 循环在 Python 中通过蛮力对其进行了编码，但我想知道它是否可以更快地完成？

位置和范围都是 1 到 1000 之间的整数

标签： dictionary

解决方案

我不知道这是否是最佳解决方案，但它应该比蛮力方法更快。关键是每个索引（1-1000）只能有一个元组，因此我们可以创建一个范围数组（1-1000），然后通过该数组搜索每个范围内的所有索引。

cnt = {} # final dictionary

# test set
lst = [(0,2),(2,3),(4,1),(8,3),(12,6),(17,30),(30,24),(35,5),(40,10),(57,60),(61,23),(75,45)]

# every entry
lstRng = [0]*1000

# entries included in tuple list
lstNonZero = []

for t in lst:  # every tuple
   lstRng[t[0]] = t[1]  # set range in full list
   lstNonZero += [t[0]]  # add to list of used indexes
   cnt[t[0]] = []  # create entry for final dictionary

for i in lstNonZero:   # all indexes that have values
   rng = lstRng[i]   # rng for that index
   cnt[i] = [z for z in lstNonZero if (abs(i-z) <= rng)] # indexes in range
   
print(cnt)

输出（格式化）

{
   0: [0, 2], 
   2: [0, 2, 4], 
   4: [4], 
   8: [8], 
  12: [8, 12, 17], 
  17: [0, 2, 4, 8, 12, 17, 30, 35, 40], 
  30: [8, 12, 17, 30, 35, 40], 
  35: [30, 35, 40], 
  40: [30, 35, 40], 
  57: [0, 2, 4, 8, 12, 17, 30, 35, 40, 57, 61, 75], 
  61: [40, 57, 61, 75], 
  75: [30, 35, 40, 57, 61, 75]
}

推荐阅读