C++ 算法实现：寻找数组中第 k 小的正整数

寻找数组中第 k 小的正整数

题目描述

现在已知 n 个正整数 a1,a2,⋯,an，请编程找出其中第 k 小的正整数。如果有相同的数，则它们各占据一个排名，例如在 1, 2, 3, 4, 4, 4, 5, 6, 7 中，第 4, 5, 6 小的数都为 4。

输入

第 1 行，两个正整数 n 和 k，表示数字的个数，以及你要找出其中第 k 小的数； 第 2 行，用空格隔开的 n 个正整数 a1,a2,⋯,an。

输出

一个正整数，即 a1,a2,⋯,an 中第 k 小的数。

样例输入

9 5
1 2 3 4 4 4 5 6 7

样例输出

4

提示

1 ≤k ≤n ≤106；1 ≤ai ≤≤ 104。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    cout << nums[k-1] << endl;
    return 0;
}

代码解释

1. 使用 vector<int> nums(n) 创建一个大小为 n 的整数向量来存储输入的数字。
2. 使用循环输入 n 个整数，并将其存入 nums 向量中。
3. 使用 sort(nums.begin(), nums.end()) 对 nums 向量进行排序。
4. 输出 nums 向量中第 k-1 个元素（因为数组下标从 0 开始）。

总结

通过使用 C++ 语言的标准库函数 sort，我们可以轻松地对数组进行排序，并找出其中的第 k 小的元素。这是一种简洁高效的解决方法。