题解 | #查找第K小数#

方法一：使用map，map默认递增排序且不允许键值重复，正好符合题目要求

方法二：使用优先队列，建立小根堆，再依次输出最小的值

方法三：使用快速排序，使用默认的递增排序即可，再依次输出最小的值

#include <iostream>
#include "map"
using namespace std;

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        map<int, int> myMap;
        while (n--) {
            int temp;
            cin >> temp;
            myMap[temp] = temp;
        }
        int k;
        cin >> k;
        auto it = myMap.begin();
        while (k > 1) {//从2到k总共有k-1个数，第k小的数正好对应迭代器位置为begin+k-1
            it++;
            k--;
        }
        cout << it->first << endl;
    }
}
// 64 位输出请用 printf("%lld")

方法二：

#include <iostream>
#include "queue"
using namespace std;
struct myInt {
    int data;
    myInt(int a) {
        data = a;
    }
    bool operator< (myInt another)const {
        return data > another.data;
    }
    bool operator!= (myInt another)const {
        return data != another.data;
    }
};
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        priority_queue<myInt> myQueue;
        while (n--) {
            int temp;
            cin >> temp;
            myQueue.push(myInt(temp));
        }
        int k;
        cin >> k;
        int count = 1;
        myInt temp = myQueue.top();
        myQueue.pop();
        while (k > 1) {//从2到k共k-1次
            if (temp != myQueue.top() ) {
                temp = myQueue.top();
                k--;
            }
            myQueue.pop();

        }
        cout << temp.data << endl;
    }
}
// 64 位输出请用 printf("%lld")

方法三：

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

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        vector<int> list;
        while (n--) {
            int temp;
            cin >> temp;
            list.push_back(temp);
        }
        sort(list.begin(), list.end());
        int k;
        cin >> k;
        int count = 1;
        int temp = list[0];
        for (int i = 1; i < list.size(); i++) {
            if (list[i] > temp) {
                count++;
                temp = list[i];
            }
            if (count == k) {
                break;
            }
        }
        cout << temp << endl;
    }
}
// 64 位输出请用 printf("%lld")