如何编写循环列表中缺失连续序列的查找函数

实现思路 #

1. 以target为基准序列，先建立元素到下标的映射，方便后续位置计算
2. 提取所有given元素在target中的下标，升序排序后得到下标列表
3. 由于是循环结构，需要在下标列表末尾追加「第一个下标 + target总长度」，用来处理跨首尾的连续缺失场景
4. 遍历相邻下标对，计算两个下标之间的差值：
   • 差值≤1时说明两个下标对应元素连续，无缺失
   • 差值>1时提取两个下标中间的所有下标，每个下标对target长度取模后映射为target的对应元素，组成缺失序列
5. 收集所有缺失序列即为最终结果

代码实现（Python版本） #

def find_cyclic_missing(target: list, given: list) -> list:
    n = len(target)
    # 建立元素到下标的映射
    val_to_idx = {v:i for i, v in enumerate(target)}
    # 提取given元素的有效下标并排序，自动过滤不在target中的异常元素
    given_indices = sorted([val_to_idx[v] for v in given if v in val_to_idx])
    # 边界处理：given为空时整个target都是缺失序列
    if not given_indices:
        return [target.copy()]
    # 补位处理循环首尾衔接的场景
    given_indices.append(given_indices[0] + n)
    res = []
    for i in range(len(given_indices)-1):
        cur_idx = given_indices[i]
        next_idx = given_indices[i+1]
        if next_idx - cur_idx > 1:
            # 中间下标模n得到实际target下标，映射为对应元素
            missing_seq = [target[idx % n] for idx in range(cur_idx + 1, next_idx)]
            res.append(missing_seq)
    return res

测试验证 #

用示例参数测试：

target = [0, 1, 2, 3, 4, 5, 6, 7]
given = [1, 2, 5, 6]
print(find_cyclic_missing(target, given))

输出结果为[[7, 0], [3, 4]]，和预期完全一致。

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