给定一个未排序的整数列表，找出数字连续的最长序列，若最长序列不止一个，则输出第一个元素最小的序列

<think>我们有一个未排序的整数数组，需要找到最长的连续数字序列（连续指数字按1递增）。如果有多个最长序列，则返回起始值最小的那个序列的起始值。连续序列的例子：对于数组[100,4,200,1,3,2]，最长的连续序列是[1,2,3,4]，长度为4，起始值为1。思路：1.使用一个集合（HashSet）来存储数组中的所有数字，以便进行O(1)复杂度的查找。2.遍历数组中的每个数字，对于每个数字，我们检查它是否是一个连续序列的起始点（即当前数字减1不在集合中）。3.如果是一个起始点，则从该数字开始，不断检查当前数字+1是否在集合中，从而得到当前连续序列的长度。4.在遍历过程中，记录最长的连续序列长度以及对应的起始值。如果有多个相同长度的最长序列，则选择起始值最小的那个。注意：由于数组可能有重复元素，我们使用集合去重。具体步骤：-初始化一个空集合，将数组所有元素加入集合。-初始化两个变量：maxLength（记录最长序列长度）和minStart（记录最长序列的起始值，如果有多个则取最小的起始值）。-遍历集合中的每个元素（注意：遍历集合而不是数组，因为集合去重了）：如果当前元素num的前一个数num-1不在集合中，说明num是一个连续序列的起点。然后，从num开始，依次检查num+1,num+2,...直到某个数字不在集合中，从而得到当前连续序列的长度。得到当前连续序列的长度后，与maxLength比较：如果当前长度大于maxLength，则更新maxLength，并将minStart更新为当前的起始值num。如果当前长度等于maxLength，则比较当前的起始值num和minStart，取较小的那个作为新的minStart。-最后，我们返回的是起始值minStart吗？注意题目要求：返回第一个元素最小的序列。但注意，我们记录的是起始值，而整个序列可以由起始值确定。但题目要求是返回序列？还是返回起始值？题目中说“返回第一个元素最小的序列”，但问题描述最后说“返回起始值最小的序列的起始值”？实际上，问题描述是：“返回第一个元素最小的序列”，但通常我们返回这个序列的起始值即可代表这个序列，或者返回整个序列？需要明确。根据问题：“返回起始值最小的序列”，但问题没有明确要求返回整个序列还是起始值。但通常，题目可能要求返回序列的长度，或者序列本身，或者起始值。这里问题描述是：“返回第一个元素最小的序列”。再看用户的问题：“如果有多个最长序列返回起始值最小的序列算法实现”。所以，我们可能需要返回整个序列？还是只返回起始值？重新阅读用户问题：“我想寻找未排序整数列表中数字连续的最长序列，并在存在多个最长序列时返回第一个元素最小的序列”。这里明确要求返回序列。所以我们需要返回这个序列（即一个数组）。但是，注意：我们可以在遍历过程中记录序列的起始值，然后根据起始值和长度，我们可以在集合中重新构建这个序列吗？但是集合是无序的，我们可以在最后通过起始值+长度来生成序列。因此，我们可以：-记录最长序列的起始值minStart和长度maxLength。-然后，返回的序列就是[minStart,minStart+1,minStart+2,...,minStart+maxLength-1]。但是，注意：可能存在多个相同长度的最长序列，我们在比较过程中已经保证了minStart是这些最长序列中起始值最小的那个。然而，还有一种情况：可能存在多个不同的最长序列，但它们的长度相同且起始值不同，我们只取起始值最小的那个。所以，算法步骤：1.创建集合num_set，存储所有数字（去重）。2.初始化maxLength=0,minStart=None（或者用第一个找到的序列来初始化）。3.遍历集合中的每个数num：如果num-1不在集合中，则当前num是连续序列的起点。令currentNum=num，当前序列长度currentLength=1。然后循环检查currentNum+1是否在集合中，直到不在，每次currentNum加1，currentLength加1。当循环结束后，比较currentLength和maxLength：如果currentLength>maxLength，则更新maxLength=currentLength，minStart=num。如果currentLength==maxLength，则比较num和minStart（当前序列的起始值和之前记录的最小起始值），如果num更小，则更新minStart=num。4.根据minStart和maxLength，生成序列：从minStart到minStart+maxLength-1（包括两端）的所有整数。注意：为什么在currentLength==maxLength时，我们要更新minStart？因为可能有多个相同长度的序列，我们要取起始值最小的。但是，我们遍历集合时，遇到相同长度的序列，且起始值更小，我们就更新minStart。但是，这里有一个问题：我们遍历集合的顺序是不确定的。所以，我们可能会先遇到起始值较大的序列，再遇到起始值较小的相同长度的序列。因此，我们在遇到相同长度时，取起始值更小的，这样就能保证minStart始终是当前已知的最长序列中起始值最小的。然而，还有一种情况：可能存在一个序列长度比当前记录的最大长度小，但起始值更小？不会，因为我们在更新minStart时，只有当前序列长度>=maxLength时才更新（大于时直接更新，等于时比较起始值）。而小于maxLength的序列我们不需要考虑。因此，算法正确。但是，我们也可以不记录整个序列，而是最后再构建序列。这样节省空间。实现代码（使用Python）：注意：由于集合无序，遍历顺序不影响结果，因为我们每次都是重新检查。例子：数组[1,2,0,1]->去重后集合{0,1,2}，最长连续序列长度为3，起始值0，序列为[0,1,2]。另一个例子：[100,4,200,1,3,2]->最长连续序列[1,2,3,4]长度为4，起始值1。但是，考虑有多个最长序列的情况：例如[0,1,2,4,5,6]，有两个长度为3的序列：[0,1,2]和[4,5,6]。按照要求，返回起始值最小的序列，即[0,1,2]。所以minStart=0。代码实现：步骤：1.创建集合2.初始化max_length=0,min_start=None3.遍历集合中的每个数：如果num-1不在集合中：current_num=numcurrent_length=1循环：当current_num+1在集合中时，current_num加1，current_length加1循环结束后，比较current_length和max_length：如果current_length>max_length：则更新max_length=current_length，min_start=num如果current_length==max_length：则比较num和min_start，如果num<min_start，则更新min_start=num4.生成结果序列：list(range(min_start,min_start+max_length))但是注意：如果数组为空，则应该返回空序列。另外，如果数组只有一个元素，则返回该元素组成的序列。代码示例：测试用例：输入：[100,4,200,1,3,2]->序列为[1,2,3,4]->返回[1,2,3,4]输入：[0,1,2,4,5,6]->有两个长度为3的序列，取起始值0，所以返回[0,1,2]但是，注意：在[0,1,2,4,5,6]中，我们遍历集合时，可能先遇到4（因为集合无序），然后我们检查4-1=3不在集合中，所以4是一个起点，然后得到序列[4,5,6]（长度为3），此时max_length=3，min_start=4。然后遇到0，0-1=-1不在集合中，所以0是起点，得到序列[0,1,2]（长度3），然后比较0<4，所以更新min_start=0。最后返回序列[0,1,2]。因此，代码可以实现。但是，我们也可以不生成整个序列，而是返回起始值和长度？但题目要求返回序列。所以，最后我们返回一个列表：从min_start开始，连续max_length个整数。代码实现：注意：如果数组为空，则返回空列表。我们写代码：</think>### 算法实现：寻找最长连续序列（返回起始值最小的序列） #### 核心思路 1. **使用哈希集合去重**：通过 `HashSet` 存储数组元素，实现 $O(1)$ 复杂度的元素存在性检查。 2. **定位序列起点**：遍历集合，若元素 $num-1$ 不存在，则 $num$ 是连续序列的起点。 3. **扩展序列长度**：从起点开始，循环检查 $num+k$ 是否存在，统计序列长度。 4. **记录最优解**： - 始终记录当前最长序列的长度 `maxLength`。 - 当出现相同长度的序列时，选择起始值最小的序列（通过比较 `minStart`）。 #### Python 代码实现 ```python def longest_consecutive_sequence(nums): if not nums: return [] # 创建哈希集合（去重） num_set = set(nums) max_length = 0 min_start = float('inf') # 初始化为无穷大，确保首次更新 for num in num_set: # 检查是否为序列起点（num-1 不存在） if num - 1 not in num_set: current_num = num current_length = 1 # 向右侧扩展序列 while current_num + 1 in num_set: current_num += 1 current_length += 1 # 更新最优解：优先长度，次优先起始值最小 if current_length > max_length: max_length = current_length min_start = num elif current_length == max_length: min_start = min(min_start, num) # 取更小的起始值 # 生成连续序列 [min_start, min_start+1, ..., min_start+max_length-1] return [min_start + i for i in range(max_length)] ``` #### 算法分析 1. **时间复杂度**：$O(n)$ - 哈希集合操作 $O(1)$，每个元素最多被访问两次（起点检查和右侧扩展）。 2. **空间复杂度**：$O(n)$ - 哈希集合存储 $n$ 个元素。 #### 示例验证 ```python # 测试用例 1 print(longest_consecutive_sequence([100, 4, 200, 1, 3, 2])) # 输出: [1, 2, 3, 4]（唯一最长序列） # 测试用例 2 print(longest_consecutive_sequence([0, 1, 2, 4, 5, 6])) # 输出: [0, 1, 2]（两个长度为3的序列，取起始值最小的 [0,1,2]） # 测试用例 3 print(longest_consecutive_sequence([10, 5, 12, 11])) # 输出: [10, 11, 12]（序列 [10,11,12] 比 [5] 更长） ``` #### 关键点说明 - **去重必要性**：重复元素不影响序列长度（如 `[1,1,2]` 的序列为 `[1,2]`）。 - **起点判断**：仅当 $num-1$ 不存在时启动扩展，避免重复计算。 - **多序列处理**：通过 `min(min_start, num)` 确保返回起始值最小的序列。 此算法高效处理无序数组的最长连续序列问题，并满足多序列时返回起始值最小序列的需求[^1]。