luogu-P1138 第 k 小整数

GESP C++四级练习（三级也可以尝试），排序与去重练习，难度⭐⭐。

luogu-P1138 第 k 小整数

题目要求

题目描述

现有 $n$ 个正整数，要求出这 $n$ 个正整数中的第 $k$ 个最小整数（相同大小的整数只计算一次）。

输入格式

第一行为 $n$ 和 $k$; 第二行开始为 $n$ 个正整数的值，整数间用空格隔开。

输出格式

第 $k$ 个最小整数的值；若无解，则输出 NO RESULT。

输入输出样例 #1

输入 #1

10 3
1 3 3 7 2 5 1 2 4 6

输出 #1

3

说明/提示

$n \leq 10000$，$k \leq 4000$，正整数均小于 $30000$。

题目分析

解题思路

本题要求在 $n$ 个正整数中，找到去重后的第 $k$ 小的整数。核心操作是排序和去重。

1. 问题分析：

   • 输入 $n$ 个正整数，其中可能包含重复元素
   • 需要在去除重复元素后，找到第 $k$ 小的整数
   • 如果去重后不足 $k$ 个不同的整数，输出 NO RESULT

2. 解题方法：

   • 排序：首先将 $n$ 个正整数从小到大排序。排序后，相同的元素会紧邻在一起，方便后续去重操作。
   • 遍历去重并计数：排序完成后，从头到尾遍历数组。遍历过程中，每遇到一个与前一个元素不同的值，就表示找到了一个新的不重复整数，将计数器加一。当计数器达到 $k$ 时，当前元素即为答案。
   • 无解判断：如果遍历完整个数组后，计数器仍未达到 $k$，则说明不同整数的总数不足 $k$ 个，输出 NO RESULT。

3. 实现要点：

   • 使用 std::sort 对数组进行排序
   • 排序后第一个元素天然是第 1 小的，因此计数器从 1 开始
   • 从第二个元素开始遍历，每当 a[i] != a[i-1] 时计数器加一
   • 注意数组大小需根据数据范围定义（$n \leq 10000$）

复杂度分析：

• 时间复杂度：$O(n \log n)$，排序是主要的时间开销
• 空间复杂度：$O(n)$，需要存储 $n$ 个整数

示例代码

#include <algorithm>
#include <iostream>

int main() {
    int n, k;
    std::cin >> n >> k;

    // 读入 n 个正整数
    int a[10001];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    // 从小到大排序
    std::sort(a, a + n);

    // 排序后第一个元素就是第 1 小的整数
    int count = 1;

    // 如果 k 为 1，直接输出排序后的第一个元素
    if (count == k) {
        std::cout << a[0] << std::endl;
        return 0;
    }

    // 从第二个元素开始遍历，遇到不同的值则计数加一
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            count++;
            if (count == k) {
                std::cout << a[i] << std::endl;
                return 0;
            }
        }
    }

    // 遍历结束仍未找到第 k 小的整数，输出无解
    std::cout << "NO RESULT" << std::endl;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号