第k小元素求解：排序取索引k-1的高效实现与常见陷阱避坑指南

这道题是经典的 **求第 k 小元素（k-th smallest element）** 问题。 --- ### ✅ 题目解析 - 给定 `n` 个**正整数**（可能重复） - 要求输出**第 k 个最小的数**（即升序排列后，下标为 `k−1` 的元素，**1-indexed**） > 🔑 注意：是「第 k 个最小」，不是「第 k 个不重复的最小」！ > 样例：`[1,3,3,7,2,5,1,2,4,6]`，排序后为： > `[1, 1, 2, 2, 3, 3, 4, 5, 6, 7]` > 第 1 小 = 1，第 2 小 = 1，**第 3 小 = 2** → ✅ 输出 `2` --- ### ✅ 解法对比（按推荐度排序） | 方法 | 时间复杂度 | 空间复杂度 | 是否去重 | 适用场景 | 备注 | |------|-------------|-------------|-----------|------------|------| | **✅ 排序 + 取 `a[k-1]`** | `O(n log n)` | `O(n)` | ❌（保留重复） | `n ≤ 10⁶` | 简洁、安全、AC首选 | | **✅ 快速选择（QuickSelect）** | 平均 `O(n)`，最坏 `O(n²)` | `O(1)` | ❌ | 追求极致性能（如 `n=5e6+`） | 实现稍复杂，易写错 | | **❌ 堆（大根堆维护前k小）** | `O(n log k)` | `O(k)` | ❌ | `k ≪ n` 时较优 | 本题 `k` 任意，不必要 | | **❌ 计数排序（因值域 1~1e6）** | `O(max_val)` | `O(max_val)` | ❌ | 若 `max_val ≤ 1e6` 且 `n` 极大（如 `1e7`），可考虑 | 本题未限定值域上限，但题目说“正整数”，稳妥起见仍推荐排序 | > 💡 **结论：对本题（n 未超 1e6），直接排序是最优解 —— 简洁、正确、不易错、OJ 100% 通过** --- ### ✅ Python AC 代码（含输入安全处理） ```python import sys def main(): data = sys.stdin.read().split() n = int(data[0]) k = int(data[1]) a = list(map(int, data[2:2+n])) a.sort() print(a[k-1]) if __name__ == '__main__': main() ``` #### ✨ 说明： - 使用 `sys.stdin.read().split()` 一次性读入所有 token，避免 `input()` 多次调用慢或换行符干扰； - `k-1` 是因为题目是 **1-indexed 第 k 小**，数组是 0-indexed； - 自动处理重复元素（排序天然支持）； #### ▶️ 验证样例： 输入： ``` 10 3 1 3 3 7 2 5 1 2 4 6 ``` → `a = [1,1,2,2,3,3,4,5,6,7]` → `a[3-1] = a[2] = 2` ✅ --- ### ⚠️ 常见错误（你可能踩过的坑） | 错误 | 表现 | 如何避免 | |------|------|-----------| | ❌ 用了 `set()` 去重再排序 | 输出 `3`（第3小不重复数）→ WA | 题目没说“不重复”，**必须保留重复** | | ❌ `print(a[k])`（忘记 `-1`） | `k=3` 时输出第4小 → WA | 牢记：**第1小 = index 0，第k小 = index k−1** | | ❌ 没排序，直接 `min()` 或遍历找第k小 | 超时 / 逻辑错 | 排序是性价比最高的方案 | | ❌ 输入读错（如只读了 `n,k`，没读后面 n 个数） | `IndexError` 或取到错误值 | 用 `data[2:2+n]` 严格截取 | --- ### 🚀 进阶：如果你追求 `O(n)`（快速选择模板，Python） ```python import random import sys def quickselect(arr, left, right, k): if left == right: return arr[left] pivot_index = random.randint(left, right) pivot_index = partition(arr, left, right, pivot_index) if k == pivot_index: return arr[k] elif k < pivot_index: return quickselect(arr, left, pivot_index - 1, k) else: return quickselect(arr, pivot_index + 1, right, k) def partition(arr, left, right, pivot_index): pivot_value = arr[pivot_index] arr[pivot_index], arr[right] = arr[right], arr[pivot_index] store_index = left for i in range(left, right): if arr[i] < pivot_value: arr[store_index], arr[i] = arr[i], arr[store_index] store_index += 1 arr[right], arr[store_index] = arr[store_index], arr[right] return store_index # 主程序（同上，仅替换核心） data = sys.stdin.read().split() n = int(data[0]); k = int(data[1]) a = list(map(int, data[2:2+n])) # 求第 k 小 → 目标索引 = k-1 result = quickselect(a, 0, n-1, k-1) print(result) ``` > ✅ 平均 `O(n)`，但常数大、有递归深度风险（Python 默认递归限制约 1000），**竞赛中排序更稳** --- ### ✅ 一句话答案： > 对 n 个正整数，**排序后取下标 `k−1` 的元素**，就是第 k 小的数。简单、高效、零歧义。 ######[AI写代码神器 | 1506点数解答 | 2026-03-24 17:58:34]