0

我正在尝试在运行时更改字典中的一系列值O(n)。其中 n 是我需要更改的范围内的元素数。

例如，如果我的字典有键的数字，并且我得到一个键范围列表 list = [ (key1,key3), (key2,key3)] 在这种情况下，如果我开始的话， d = {key1: odd , key2: even, key3: odd , key4: even} 那么我将在第一个范围之后 d = {key1: even , key2: odd, key3: even , key4: even} 在第二个键范围之后 d = {key1: even , key2: even, key3: odd , key4: even}

可以在python中实现吗？

4

2 回答 2

1

你可以这样做。这是 O(n)，其中 n 是您需要更改的键数。

change_keys = (1,2)
for key in change_keys:
    d[key] = 'odd' if d[key]=='even' else 'even'

如果您有范围无元组列表，例如：

key_ranges = [(2,6), (4,8)]
key_ranges = [ range(a[0],a[1]) for a in key_ranges ]

我相信你可以使用：

change_keys = set.union(*map(set,key_ranges))

但是，当然，它需要操作来生成集合。但在某些时候，您要么必须复制密钥，要么找到重复项。不确定是否可以避免。

或者，如果您想做重复项，则永远不要调用set：

key_ranges = [(2,6), (4,8)]
change_keys = []
for a in key_ranges:
    change_keys.extend(range(a[0],a[1])
于 2013-03-06T03:44:37.340 回答
0

如果你真正的意思是 n 是范围列表的长度，那么没有办法使用字典来实现这一点。例如，如果范围是 [(0,100000000000)]，那么在字典中执行此操作将相对于范围列表中的位数呈指数增长。

如果您选择了正确的数据表示和算法，您可以在 nlogn 中实现您的操作，其中 n 是范围列表的长度。相对于范围内的实际元素数量，这通常比 O(n) 的运行时间快得多。

这是一个可能的解决方案：

  1. 定义一个由范围列表组成的数据结构。列表中某个范围内的元素已从其原始起始状态“翻转”。

  2. 定义一个例程，将一组新的翻转（传入范围列表）与现有的“合并”，并找到不相交的翻转集。

例程应该：

  1. 将数据结构的范围与传入的范围列表合并。
  2. 找到具有最小第一个元素的范围集，称为 A。
  3. 找到在 A 中最后一个范围结束之前开始的范围集，将其与 A 合并。
  4. 根据第一个元素对 A 中的范围进行排序。
  5. 对于 A 中的每个 (b1,?)，将 A 中的每个范围 (a,b) 拆分为 (a,b1) 和 (b1,b)。A 中的范围现在应该是不重叠的。
  6. 删除所有 (a,b) 对。(a,b) 现在在 A 中应该是唯一的。
  7. 将所有范围 (a,b), (b,c) 连接到 A 中的 (a,c) 中。
  8. 将 A 添加到数据结构中。转到第 2 步，从尚未添加的下一个最小元素开始。
于 2013-03-06T04:36:34.817 回答