Python教程：高效统计列表中子序列的出现次数

理解问题：序列查找与计数

在python编程中，我们经常需要处理列表（或数组）数据。一个常见的需求是检查一个较短的序列（子序列）是否包含在一个较长的列表（主列表）中。然而，仅仅判断子序列是否存在往往不足够，我们可能还需要知道它在主列表中总共出现了多少次。

例如，如果我们有一个主列表 ['A','V','V','V','V','V','E','A','V','V'] 和一个目标子序列 ['A','V','V']，我们希望得到的结果是 2，因为 ['A','V','V'] 在主列表中连续出现了两次。

直接使用如 any(target_sequence == main_list[i:i + n] for i in range(len(main_list) - n + 1)) 这样的方法，虽然可以判断是否存在，但它会在找到第一个匹配项时立即停止并返回 True，无法统计所有出现次数。因此，我们需要一种更精确的计数策略。

核心解决方案：滑动窗口与切片比较

解决这个问题的核心思想是采用“滑动窗口”的方法。我们定义一个与目标子序列长度相同的“窗口”，让这个窗口在主列表上从头到尾滑动。在每一步滑动中，我们截取窗口当前覆盖的子列表，并将其与目标子序列进行比较。如果两者完全匹配，我们就增加一个计数器。

具体步骤如下：

立即学习“Python免费学习笔记（深入）”；

1. 确定目标长度： 获取目标子序列的长度 n。
2. 初始化计数器： 设置一个变量 x，用于存储匹配次数，初始值为 0。
3. 遍历主列表： 使用一个循环，从主列表的第一个元素开始，到 len(主列表) - n + 1 结束。这个范围确保了每次切片都能得到一个完整长度为 n 的子列表，且不会超出主列表的边界。
4. 切片与比较： 在循环的每一步 i，从主列表中切取一个子列表 main_list[i : i + n]。然后，将这个切片与目标子序列进行比较。
5. 累加计数： 如果切片与目标子序列相等，则将计数器 x 1。

实战代码示例

以下是根据上述逻辑实现的Python代码示例：

# 定义主列表和目标子序列
main_list = ['A','V','V','V','V','V','E','A','V','V']
target_sequence = ['A','V','V']

# 获取目标子序列的长度
n = len(target_sequence)

# 初始化计数器
count = 0

# 遍历主列表，使用滑动窗口进行比较
for i in range(len(main_list) - n + 1):
    # 切取当前窗口内的子列表
    current_slice = main_list[i : i + n]

    # 比较切片与目标子序列
    if current_slice == target_sequence:
        count += 1 # 如果匹配，计数器加1

# 输出结果
print(f"子序列 {target_sequence} 在主列表 {main_list} 中出现了 {count} 次。")

输出：

子序列 ['A', 'V', 'V'] 在主列表 ['A', 'V', 'V', 'V', 'V', 'V', 'E', 'A', 'V', 'V'] 中出现了 2 次。

代码解析与执行流程

让我们逐步分析上述代码在示例数据上的执行过程：

• main_list = ['A','V','V','V','V','V','E','A','V','V']
• target_sequence = ['A','V','V']
• n = 3 (因为 len(['A','V','V']) 是 3)
• count = 0

循环 for i in range(len(main_list) - n + 1)，即 for i in range(10 - 3 + 1)，也就是 for i in range(8)，i 将从 0 遍历到 7。

1. i = 0:

   

   bee餐饮点餐外卖小程序

   bee餐饮点餐外卖小程序是针对餐饮行业推出的一套完整的餐饮解决方案，实现了用户在线点餐下单、外卖、叫号排队、支付、配送等功能，完美的使餐饮行业更高效便捷！功能演示：1、桌号管理登录后台，左侧菜单 “桌号管理”，添加并管理你的桌号信息，添加以后在列表你将可以看到 ID 和 密钥，这两个数据用来生成桌子的二维码2、生成桌子二维码例如上面的ID为 308，密钥为 d3PiIY，那么现在去左侧菜单微信设置

   1

   查看详情
   • current_slice = main_list[0:3] 得到 ['A','V','V']。
   • ['A','V','V'] == ['A','V','V'] 为 True。
   • count 变为 1。

2. i = 1:

   • current_slice = main_list[1:4] 得到 ['V','V','V']。
   • ['V','V','V'] == ['A','V','V'] 为 False。
   • count 保持 1。

3. i = 2:

   • current_slice = main_list[2:5] 得到 ['V','V','V']。
   • ['V','V','V'] == ['A','V','V'] 为 False。
   • count 保持 1。

4. i = 3:

   • current_slice = main_list[3:6] 得到 ['V','V','E']。
   • ['V','V','E'] == ['A','V','V'] 为 False。
   • count 保持 1。

5. i = 4:

   • current_slice = main_list[4:7] 得到 ['V','E','A']。
   • ['V','E','A'] == ['A','V','V'] 为 False。
   • count 保持 1。

6. i = 5:

   • current_slice = main_list[5:8] 得到 ['E','A','V']。
   • ['E','A','V'] == ['A','V','V'] 为 False。
   • count 保持 1。

7. i = 6:

   • current_slice = main_list[6:9] 得到 ['A','V','V']。
   • ['A','V','V'] == ['A','V','V'] 为 True。
   • count 变为 2。

8. i = 7:

   • current_slice = main_list[7:10] 得到 ['V','V',]。
   • ['V','V',] == ['A','V','V'] 为 False。
   • count 保持 2。

循环结束，最终 count 的值为 2，这正是我们期望的结果。

注意事项与性能考量

• 时间复杂度： 这种方法的平均时间复杂度是 O(N * M)，其中 N 是主列表的长度，M 是目标子序列的长度。这是因为外层循环执行了 N-M+1 次，而每次循环内部的列表切片和比较操作在最坏情况下需要 M 次元素比较。对于大多数常见的列表长度，这种性能是完全可以接受的。
• 空间复杂度： 每次切片会创建一个新的子列表，其空间复杂度为 O(M)。
• 空序列处理： 如果 target_sequence 是一个空列表 []，那么 n 将为 0。此时 range(len(main_list) - 0 + 1) 会导致循环执行 len(main_list) + 1 次。main_list[i:i+0] 始终是 []，所以它会匹配所有可能的位置。如果需要特殊处理空序列，应在函数开头添加一个条件判断。
• 可读性： 这种方法代码直观、易于理解，符合Python的简洁风格。

总结

通过采用滑动窗口和列表切片比较的方法，我们可以有效地在Python列表中查找并统计特定子序列的出现次数。这种方法简单、直接，并且对于大多数应用场景而言，提供了足够的性能。理解其背后的原理和执行流程，有助于我们更好地解决类似的序列处理问题。

以上就是Python教程：高效统计列表中子序列的出现次数的详细内容，更多请关注php中文网其它相关文章！