P1138 第k小整数（unique去重）

题目描述

现有n个正整数，n≤10000，要求出这nn个正整数中的第kk个最小整数（相同大小的整数只计算一次），k≤1000，正整数均小于30000。

输入格式

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

输出格式

第kk个最小整数的值；若无解，则输出“NO RESULT”。

输入输出样例
输入
10 31 3 3 7 2 5 1 2 4 6

输出
3

说明/提示
n≤10000

思路：原谅自己写的代码比较搓，sort之后还用循环去找第k大的数。
后面看了别人的代码之后，发现可以在先sort之后用unique函数对数组去重，然后直接输出第k小的数，进而提高运行的效率。

#include<bits/stdc++.h>
using namespace std;

int a[10009];
int main()
{
    int n,k;
    cin>>n>>k;
    int flag=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    int count1=1;
    int x;
    for(int i=1;i<n;i++)
    {
        if(a[i]>a[i-1])
        {
            count1++;
            x=i;
        }
        if(count1==k)
        {
            flag=1;
            break;
        }
    }
    if(flag)
    {
        cout<<a[x]<<endl;
    }
    else
    {
        cout<<"NO RESULT"<<endl;
    }
    return 0;
}

在STL中unique函数是一个去重函数， unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中，然后 返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。
注意，words的大小并没有改变，依然保存着10个元素；只是这些元素的顺序改变了。调用unique“删除”了相邻的重复值。给“删除”加上引号是因为unique实际上并没有删除任何元素，而是将无重复的元素复制到序列的前段，从而覆盖相邻的重复元素。unique返回的迭代器指向超出无重复的元素范围末端的下一个位置。``
注意：算法不直接修改容器的大小。如果需要添加或删除元素，则必须使用容器操作。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10003];//定义变量和数组
int main()
{
    cin>>n>>k;
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a,a+n);//快排数组a
    int ans=unique(a,a+n)-a;//给数组a去重，并保留ans=去重后非伪的长度
    if(k<ans)
        cout<<a[k-1]; //如果去重以后k<=ans，则输出对应的数
    else
        cout<<"NO RESULT";//否则输出 NO RESULT
    return 0;
}

下面还有一题类似的
P1059 明明的随机数
题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了NN个11到10001000之间的随机整数(N≤100)(N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第11行为11个正整数，表示所生成的随机数的个数NN

第22行有NN个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第11行为11个正整数MM，表示不相同的随机数的个数。

第22行为MM个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入输出样例

输入 #1 复制
10
20 40 32 67 40 20 89 300 400 15
输出 #1 复制
8
15 20 32 40 67 89 300 400
说明/提示

NOIP 2006 普及组 第一题

#include<bits/stdc++.h>
using namespace std;
int n,a[1009];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    int t=unique(a+1,a+n+1)-a-1;//这里t表示去重后还剩多少个数，记得减去前端点，记住就行
    cout<<t<<endl;
    for(int i=1; i<=t; i++)
        cout<<a[i]<<" ";
    return 0;
}