如何高效基于元素出现次数动态插入数据至有序结构？

需求回顾 #

• 持续生成新数据，需维护一个有序结构
• 排序规则：
  1. 出现次数更少的元素排在前面（这里的“出现次数”指元素本次插入前的累计出现次数+1，即该次插入对应的次数组）
  2. 出现次数相同时，严格保持元素的生成顺序（即该次插入的先后顺序）
• 要求在线式插入：每次生成数据后直接插入到正确位置，避免全量重排（数据量极大时全量重排效率极低）

现有方案问题 #

你编写的rearrange函数是离线式全量重排逻辑，虽然结果符合需求，但每次插入后都重新遍历整个列表生成新结构，数据量增大时时间复杂度会达到O(n²)，无法满足高效需求。

解决方案 #

方案1：列表+有序频率字典（中小数据量适用） #

通过维护元素计数和次数对应的元素数量，快速计算插入位置，直接在列表中插入。

from collections import defaultdict
from sortedcontainers import SortedDict
import random

# 记录每个元素当前的累计出现次数（插入前的次数）
counts = defaultdict(int)
# 有序字典：键为次数，值为该次数对应的元素总数
freq = SortedDict()
# 存储最终有序结构的列表
ordered_list = []

def insert_element(x):
    current_count = counts[x]
    new_count = current_count + 1
    
    # 更新旧次数的元素总数
    if current_count > 0:
        freq[current_count] -= 1
        if freq[current_count] == 0:
            del freq[current_count]
    
    # 计算插入位置：所有次数小于new_count的元素总数之和
    insert_idx = freq.bisect_left(new_count)
    insert_pos = sum(freq.values()[:insert_idx])
    
    # 插入到列表的对应位置
    ordered_list.insert(insert_pos, x)
    
    # 更新新次数的元素总数和元素计数
    counts[x] = new_count
    freq[new_count] = freq.get(new_count, 0) + 1

# 测试生成并插入50个随机数
for _ in range(50):
    num = random.randint(0, 10)
    insert_element(num)

print(ordered_list)

方案2：分块链表（大数据量适用） #

用多个双端链表分别存储不同次数组的元素，配合有序集合维护次数顺序，插入操作仅需将元素追加到对应链表末尾，效率极高。

from collections import defaultdict, deque
from sortedcontainers import SortedList
import random

# 记录每个元素当前的累计出现次数（插入前的次数）
counts = defaultdict(int)
# 有序集合：维护从小到大的次数值
sorted_freqs = SortedList()
# 字典：键为次数，值为对应次数组的双端链表
freq_deques = defaultdict(deque)

def insert_element(x):
    current_count = counts[x]
    new_count = current_count + 1
    
    # 如果新次数不在有序集合中，添加进去
    if new_count not in sorted_freqs:
        sorted_freqs.add(new_count)
    
    # 将元素追加到对应次数组的链表末尾
    freq_deques[new_count].append(x)
    
    # 更新元素计数
    counts[x] = new_count

# 获取完整的有序结构列表
def get_ordered_list():
    result = []
    for freq in sorted_freqs:
        result.extend(freq_deques[freq])
    return result

# 测试生成并插入50个随机数
for _ in range(50):
    num = random.randint(0, 10)
    insert_element(num)

print(get_ordered_list())

方案说明 #

• 方案1的插入时间复杂度为O(log m + n)，其中m是不同次数的数量，n是当前元素总数。列表插入需要移动元素，适合中小数据量场景。
• 方案2的插入时间复杂度为O(log m)，仅需操作链表和有序集合，无需移动已有元素，适合数据量极大的场景，遍历整个结构时再拼接所有链表即可。

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