为每个位置分配最长连续匹配ID的高效方法

核心思路 #

原解法在最后一步逐个位置更新最大覆盖长度和对应Match ID，当数据量较大时效率偏低。我们可以利用差分数组实现区间批量更新，大幅减少操作次数，同时避免内存占用过高的问题。

步骤说明 #

1. 收集每个Match ID对应的所有Position，并整理为连续区间（与原解法第一步逻辑一致）。
2. 为每个区间记录其覆盖长度（end - start + 1），通过差分数组标记每个区间的长度变化：
   • 在start位置添加当前长度与对应Match ID的候选记录
   • 在end + 1位置添加撤销该候选的标记
3. 遍历所有Position，维护当前的最大覆盖长度及对应Match ID，完成最终分配。

Python实现代码 #

from collections import defaultdict

text = """Position  matches
1         1, 5, 8
2         1, 10, 30
3         10, 40, 70
4         1, 10, 90, 100, 200, 203, 300"""

# 步骤1：收集每个Match ID对应的位置列表
match_positions = defaultdict(list)
max_position = 0

for line in text.splitlines()[1:]:
    pos_str, matches_str = line.split("         ")
    pos = int(pos_str)
    max_position = max(max_position, pos)
    for match_id in map(int, matches_str.split(", ")):
        match_positions[match_id].append(pos)

# 步骤2：将每个Match的位置转换为连续区间
intervals = []
for match_id, positions in match_positions.items():
    positions.sort()  # 兼容无序输入
    start = positions[0]
    end = positions[0]
    for p in positions[1:]:
        if p == end + 1:
            end = p
        else:
            intervals.append((match_id, start, end))
            start = p
            end = p
    intervals.append((match_id, start, end))

# 步骤3：用差分数组处理区间更新
diff = [[] for _ in range(max_position + 2)]  # 预留end+1的处理位置

for match_id, start, end in intervals:
    length = end - start + 1
    diff[start].append((length, match_id))
    diff[end + 1].append((-length, match_id))

# 步骤4：遍历位置，维护当前最优Match ID
current_candidates = defaultdict(int)
best_match = 0
result = [0] * (max_position + 1)

for pos in range(1, max_position + 1):
    # 更新当前候选池
    for delta, mid in diff[pos]:
        if delta > 0:
            current_candidates[mid] = delta
        else:
            del current_candidates[mid]
    
    # 筛选当前覆盖最长的Match ID
    if current_candidates:
        current_max_len = max(current_candidates.values())
        for mid, length in current_candidates.items():
            if length == current_max_len:
                best_match = mid
                break
    result[pos] = best_match

# 输出结果
print("Position  match ID")
for pos in range(1, max_position + 1):
    print(f"{pos:<9} {result[pos]}")

优化点说明 #

1. 时间效率提升：原解法最后一步时间复杂度为O(M)（M为所有区间的总位置数），优化后变为O(N + P)（N为区间数量，P为最大Position值），在大Position场景下效率提升显著。
2. 内存占用优化：无需预生成全量矩阵，仅用差分数组和结果数组，内存占用与最大Position值线性相关，避免了全量矩阵的高额内存开销。
3. 鲁棒性增强：代码中增加了positions.sort()，即使输入的Position无序也能正确处理。

Julia实现（可选） #

using DataStructures

# 输入数据
text = """Position  matches
1         1, 5, 8
2         1, 10, 30
3         10, 40, 70
4         1, 10, 90, 100, 200, 203, 300"""

# 步骤1：收集每个Match ID的位置
match_positions = DefaultDict{Int, Vector{Int}}(() -> Int[])
max_position = 0

for line in split(text, '\n')[2:end]
    parts = split(line, "         ")
    pos = parse(Int, parts[1])
    max_position = max(max_position, pos)
    matches = parse.(Int, split(parts[2], ", "))
    for mid in matches
        push!(match_positions[mid], pos)
    end
end

# 步骤2：生成连续区间
intervals = []
for (mid, positions) in match_positions
    sort!(positions)
    start = positions[1]
    end_pos = positions[1]
    for p in positions[2:end]
        if p == end_pos + 1
            end_pos = p
        else
            push!(intervals, (mid, start, end_pos))
            start = p
            end_pos = p
        end
    end
    push!(intervals, (mid, start, end_pos))
end

# 步骤3：差分数组处理
diff = [[] for _ in 1:(max_position + 2)]
for (mid, start, end_pos) in intervals
    len = end_pos - start + 1
    push!(diff[start], (len, mid))
    push!(diff[end_pos + 1], (-len, mid))
end

# 步骤4：遍历计算结果
current_candidates = DefaultDict{Int, Int}(0)
best_match = 0
result = zeros(Int, max_position)

for pos in 1:max_position
    # 更新候选池
    for (delta, mid) in diff[pos]
        if delta > 0
            current_candidates[mid] = delta
        else
            delete!(current_candidates, mid)
        end
    end
    # 筛选当前最优Match ID
    if !isempty(current_candidates)
        current_max = maximum(values(current_candidates))
        for (mid, len) in current_candidates
            if len == current_max
                best_match = mid
                break
            end
        end
    end
    result[pos] = best_match
end

# 输出结果
println("Position  match ID")
for pos in 1:max_position
    println(lpad(pos, 9), " ", result[pos])
end

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