Python 青蛙过河编程题：如何巧用集合（Set）高效求解最早过河时间233

为了更好地符合搜索习惯，我为您优化了标题。

大家好，我是你们的编程知识博主！今天，我们要聊一个非常经典且有趣的算法问题——“青蛙过河”。这个问题不仅经常出现在面试中，更是考察我们对数据结构选择和算法优化能力的好机会。别看名字听起来像童话，它背后蕴含的编程智慧可不小哦！我们将深入探讨这个问题，并用 Python 语言演示如何巧妙地利用集合（Set）数据结构，以高效的方式找到青蛙最早的过河时间。

一、青蛙过河：问题背景与挑战

想象一下，有一只小青蛙，它想从河岸的一端跳到另一端。河的宽度是 `X`。青蛙只能踩着树叶过河。我们知道，河里不是一开始就有叶子的，而是随着时间的推移，不断有树叶掉落到河里的不同位置。现在，我们得到了一个数组 `A`，其中 `A[K]` 代表在第 `K` 秒时，有一片树叶掉落到了位置 `A[K]`。

青蛙要想成功过河，必须保证从位置 `1` 到位置 `X` 之间的所有位置上都至少有一片树叶作为垫脚石。我们的任务就是：找出青蛙最早能在哪一秒过河？如果青蛙永远无法过河，则返回 `-1`。

让我们用一个具体的例子来理解：
假设河的宽度 `X = 5`。
落叶序列 `A = [1, 3, 1, 4, 2, 3, 5, 4]`。

我们来模拟一下过程：
第 0 秒：没有叶子。
第 1 秒：叶子落在位置 `A[0] = 1`。目前覆盖的位置集合是 `{1}`。
第 2 秒：叶子落在位置 `A[1] = 3`。目前覆盖的位置集合是 `{1, 3}`。
第 3 秒：叶子落在位置 `A[2] = 1`。位置 `1` 已被覆盖。目前覆盖的位置集合是 `{1, 3}`。
第 4 秒：叶子落在位置 `A[3] = 4`。目前覆盖的位置集合是 `{1, 3, 4}`。
第 5 秒：叶子落在位置 `A[4] = 2`。目前覆盖的位置集合是 `{1, 2, 3, 4}`。
第 6 秒：叶子落在位置 `A[5] = 3`。位置 `3` 已被覆盖。目前覆盖的位置集合是 `{1, 2, 3, 4}`。
第 7 秒：叶子落在位置 `A[6] = 5`。目前覆盖的位置集合是 `{1, 2, 3, 4, 5}`。

在第 7 秒时，从 `1` 到 `5` 的所有位置都已被叶子覆盖。所以，青蛙最早能在第 7 秒过河。我们需要返回的答案就是 `6`（因为数组索引是从 0 开始的，所以时间是 `time + 1`，或者直接返回 `time`）。

这个问题的挑战在于，随着时间的推移，我们需要高效地判断所有必要的叶子是否已经到位，并且要找到“最早”的那个时间点。

二、朴素解法：为什么效率低下？

初次面对这个问题，你可能会想到一个直观但效率不高的方案：
从 `A` 数组的第一个元素开始，逐秒模拟。
在每一步（每秒），都遍历一遍当前已经落下的所有叶子的位置。
然后检查从 `1` 到 `X` 的所有位置是否都被覆盖了。

这种方法在每秒都需要进行大量的检查。如果 `A` 数组有 `N` 个元素（即有 `N` 秒），那么在最坏情况下，我们可能需要检查 `N` 次。而每次检查又可能需要遍历当前已落下的叶子（最多 `N` 片），并对这 `X` 个位置进行判断。这样算下来，时间复杂度可能高达 `O(N^2 * X)`，对于大型数据集来说，这几乎是不可接受的。

症结在于：我们反复地检查那些已经确认有叶子的位置，并且每次都从头开始计算。我们需要一种更智能的方式来跟踪“已覆盖的位置”。

三、核心思路：利用集合（Set）的优势

既然传统的检查效率不高，那我们换个角度思考：我们真正关心的是哪些位置“首次”被覆盖，以及当我们收集到所有从 `1` 到 `X` 的位置时，是哪一秒。

这里，Python 的 `set`（集合）数据结构就能大显身手了！`set` 有两个非常适合解决此问题的特性：
自动去重：当我们把一个元素添加到集合中时，如果这个元素已经存在，集合不会重复添加，而是保持不变。这完美符合我们只关心“某个位置是否被覆盖”的需求，而不关心它被覆盖了多少次。
快速查找与添加：向集合中添加元素 (`add()`) 或检查元素是否存在 (`in`) 的平均时间复杂度是 `O(1)`。

基于 `set` 的这些特性，我们可以设计如下算法：
创建一个空的集合 `covered_positions`，用于存储所有已被叶子覆盖且在 `1` 到 `X` 范围内的位置。
遍历数组 `A`。由于 `A` 的索引代表时间，我们可以用 `enumerate` 函数同时获取时间和叶子的位置。
对于 `A` 中的每一个叶子位置 `pos`（在时间 `time` 掉落）：

首先，判断这片叶子是否落在河的有效范围内（即 `1

2026-03-02

下一篇：Python函数求值：从基础到进阶，轻松玩转数学计算！