1.题目描述

?Time Limit: 1000 ms
Memory Limit: 256 mb

查找一个数组的第K小的数，注意同样大小算一样大。 如 2 1 3 4 5 2 第三小数为3。

输入输出格式

输入描述:

输入有多组数据。
每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。

输出描述:

输出第k小的整数。

输入输出样例

输入样例#:

6
2 1 3 5 2 2
3

输出样例#:

3

题目来源
北京邮电大学

2.题解

注意这一题不同于【深基9.例4】求第 k 小的数， 因为题目要求查找一个数组的第K小的数，注意同样大小算一样大

2.1 set集合去重 + nth_element寻找第k小的数

思路

这里因为nth_element会将重复的数也纳入计算，所以先要进行去重
这里使用set去重后，nth_element要求连续数组，所以还要将set转化为vector数组

代码

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

int main() {
    int n;
    while (cin >> n) {
    	// 注意这里nth_element将重复的数每个都进行了计数，与题目要求的只看成一个不符，所以这里进行去重 
        set<int> unique_numbers;
        for (int i = 0; i < n; ++i) {
            int number;
            cin >> number;
            unique_numbers.insert(number);
        }
        int k;
        cin >> k;

        // 将set转换为vector
        vector<int> numbers(unique_numbers.begin(), unique_numbers.end());
        // 使用 nth_element(只能使用连续的vector数组) 进行部分排序!!! 
        nth_element(numbers.begin(), numbers.begin() + k - 1, numbers.end());
        // 输出第 k 小的元素
        cout << numbers[k - 1] << endl;
    }
    return 0;
}

2.2 sort排序 + unique（形式去重，只是将重复元素全部放到数组末尾了）

思路

先排好，再去重，然后直接定位第k位即可！

代码

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

int main(){
    int n, k, a[100];
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i];
    sort(a+1,a+1+n);           // 先排好
    unique(a+1,a+1+n);      // 再去重
    cin>>k;
    cout<<a[k]<<endl;
    return 0;
 }

2.3 分治算法 //TODO

思路

参考【深基9.例4】求第 k 小的数， 暂时没想清楚

代码