当前位置 博文首页 > 可惜浅灰的博客：去重函数unique应用：洛谷P1138 第k小整数
题目描述：
? ??现有n个正整数，n≤10000，要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次），k≤1000，正整数均小于30000。
? ? 输入：第一行为nn和kk; 第二行开始为nn个正整数的值，整数间用空格隔开。
? ? 输出：第kk个最小整数的值；若无解，则输出“NO RESULT”。
解题思路：
? ? ? 显然输入是个一维串，但是题目中有说明：相同值的元素只能算一次，所以需要把相同值的元素只保留一个，剩下的去掉，使用去重函数unique；
? ? ? 去重函数只能去掉相邻的同值元素，使用unique必须先排序、再去重。去重后返回的指针，是去重后数组的尾指针，要用clear或者resize把该指针后面的重复元素截掉。
? ? ? 去重完毕后，按照输入的k找到k-1下标对应的元素即可
代码实现：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
vector<int> v;
int main()
{
int n = 0, k = 0;
int temp = 0;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> temp;
v.push_back(temp);
}
sort(v.begin(), v.end());
auto unique_end = unique(v.begin(), v.end());
v.resize(unique_end - v.begin());
if (k > v.size())
{
cout << "NO RESULT" << endl;
}
else
{
cout << v[k - 1] << endl;
}
return 0;
}