Problem J44: Find the Second Smallest / 寻找第二小的问题

版权信息： · 分治法 & 基础数组题

任务总览

题目描述

在许多实际场景中，经常需要找出“第二名”或者“第二小”的数，例如：

• 排名第二的成绩；
• 第二低的温度读数；
• 第二小的股价涨幅。

现在，给你一个长度为 $n$ 的整数序列，请你找出其中的 第二小的整数 并输出。

输入格式

*第 $1$ 行：一个正整数 $n$，表示整数序列的长度（$2 \leq n \leq 1000$）；

• 第 $2$ 行：$n$ 个整型范围内的整数，表示该序列。

输出格式

输出一个整数，为该序列中 ​ 第二小的值 ​。

输入输出样例

输入示例

10
45 785 15 65 439 62 168 6 521 36

输出示例

15

题目分析与解法

✅ 方法一：顺序遍历（推荐）

1. 初始化两个变量 min1 和 min2：

• min1 存最小值；
• min2 存第二小值；

2. 遍历数组，更新 min1 和 min2：

• 如果当前值 < min1：更新 min2 = min1, 再更新 min1 = 当前值；

  • 否则如果当前值 < min2 且 ≠ min1：更新 min2；
  3. 遍历结束后，输出 min2 即可。
  • ​ 时间复杂度 ​：$O(n)$，一次扫描即可；
  • ​ 空间复杂度 ​：$O(1)$。

  ---

  ✅ 方法二：分治法（二分分组）

  1. 将数组分为两组；
  2. 各组找出最小值与次小值；
  3. 将两组的结果合并，在这 四个数 中找出全局最小和次小；
  4. 返回次小结果。
  • 虽不比顺序法快，但体现了分治思想；
  • 实现上也可用于并行处理优化。