按顺序更改字典中的项目范围O（n）

Question

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

例如，如果我的字典里有号码键，和我得到的钥匙 名单=范围列表[（密钥1，密钥3），（密钥，密钥3）]在这种情况下 如果我开始与 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中实现？

Answer 1

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

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

我希望我没有做功课，但这里是解决方案：

1. 定义包括范围列表的数据结构。属于列表范围内的元素已从原始起始状态“翻转”。

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

例程应：

1. 合并的数据结构的范围与进入的范围列表中。
2. 找到一组具有最小第一个元素的范围，称之为A.
3. 查找在A结束的最后一个范围之前开始的一组范围，将其与A合并。
4. 根据第一个元素对A中的范围进行排序。
5. 将A中的每个范围（a，b）分解为（a，b1）和（b1，b），对于A中的每个（b1，？）.A中的范围现在应该是不重叠的。
6. 删除（a，b）的所有对。 （a，b）在A中现在应该是唯一的。
7. 在A中将所有范围（a，b），（b，c）连接成（a，c）。
8. 将A添加到数据结构。转到第2步，从尚未添加的下一个最小元素开始。

Answer 2

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

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

---

如果你有范围tupless的列表，如：

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])