如何以O(len(x))复杂度实现稀疏字典转固定长度目标字典？

给定固定大小n和稀疏键值对字典x，需要生成一个包含1到n所有索引的字典y——若索引在x的键中则取对应值，否则填入-1。

原实现代码（O(n)复杂度）：

n = 10  
# 键的有效范围是[1,10]，值可以是任意正整数
x = {1:231, 2:341, 5:123} 
y = {i+1:x[i+1] if i+1 in x else -1 for i in range(n)}

输出结果：

{1: 231, 2: 341, 3: -1, 4: -1, 5: 123, 6: -1, 7: -1, 8: -1, 9: -1, 10: -1}

当n极大时，原O(n)的遍历方式会带来明显性能开销，以下是几种更简洁高效的实现方式：

1. 基础字典覆盖法（代码更简洁） #

先创建一个所有键对应值为-1的基础字典，再用x中的键值对覆盖，代码简洁直观：

n = 10
x = {1:231, 2:341, 5:123}
y = dict.fromkeys(range(1, n+1), -1)
y.update(x)

这种方式时间复杂度仍是O(n)，但代码比原字典推导式更易读，且update操作是O(len(x))，整体效率略优于原实现。

2. 利用pandas高效处理（适合大数据场景） #

如果是在pandas/数据处理场景中，可借助Series的reindex方法实现，底层优化后的操作在大数据量下性能更优：

import pandas as pd

n = 10
x = {1:231, 2:341, 5:123}
y = pd.Series(x).reindex(range(1, n+1), fill_value=-1).to_dict()

这种方式无需手动遍历，pandas内部实现会更高效地处理稀疏到完整的转换，尤其当n极大时优势明显。

关于O(len(x))复杂度的说明 #

要生成包含1到n所有键的完整字典，必然需要初始化n个键的存储空间，因此理论上无法做到纯O(len(x))的时间复杂度——因为最终字典的大小是n，初始化或填充这些键的操作至少是O(n)。但如果你的场景不需要显式生成完整字典，仅需在查询时返回对应值（比如编码/嵌入场景的按需取值），可以用自定义逻辑实现：

from collections import defaultdict

class RangeDict(defaultdict):
    def __init__(self, n, default_val=-1, *args, **kwargs):
        super().__init__(default_val, *args, **kwargs)
        self.n = n
    
    def __getitem__(self, key):
        if not (1 <= key <= self.n):
            raise KeyError(f"Key must be between 1 and {self.n}")
        return super().__getitem__(key)

# 使用示例
n = 10
x = {1:231, 2:341, 5:123}
y = RangeDict(n, -1, x)
print(y[3])  # 输出-1
print(y[1])  # 输出231

这种方式无需预先生成n个键的字典，仅在查询时处理，实际初始化操作复杂度为O(len(x))，适合n极大但实际查询次数有限的场景。

内容的提问来源于stack exchange，提问作者alvas