CPP72 找到数组里的第k大数(C++) 题目描述 给出一个包含n个整数的数组a,使用vector存储。用STL算法实现输出数组的第k大数。 输入描述： 第一行两个整数n ,k。(1≤k≤n) 第二行n个整数表示数组a。 输出描述： 输出一个数表示答案。 示例 输入：10 2 22 30 99 98 41 69 3 47 40 97 输出：22 c++代码实现

下面是使用STL算法实现输出数组第k大数的C++代码：

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

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    nth_element(a.begin(), a.begin() + k - 1, a.end(), greater<int>());
    cout << a[k - 1] << endl;

    return 0;
}

使用nth_element函数，将数组部分排序，使得第k大的元素排在数组的第k-1个位置上，最后输出该元素即可。

相关问题

# 质数 ## 题目描述 给定两个正整数 $a$ 和 $b$，你可以对这两个数执行如下操作： $1$、选定一个质数 $p$ $2$、让大数减去这个质数 $p$，可以多次减 最后使得 $a$ 和 $b$ 的值相等 现在只需要你对给定的 $a$ 和 $b$，回答是否能找到这个质数 $p$ 注意本题有多组数据 ## 输入格式 程序输入 $T+1$ 行 第一行一个正整数，表示数据组数 $T$ 接下来 $T$ 行，每行两个正整数，表示 $a$ 和 $b$，中间以空格隔开 ## 输出格式 程序输出 $T$ 行 对每组测试数组，若能找到这个质数 $p$，输出 $“YES”$，否则输出 $“NO”$ ## 样例 #1 ### 样例输入 #1 ``` 4 100 98 42 32 4399 100 41 40 ``` ### 样例输出 #1 ``` YES YES YES NO ``` ## 提示 对 $10$% 的数据，$T=1$ 对另外 $20$% 的数据，$T≤100$ 对 $100$% 的数据，$T≤1,000，1≤a，b≤10^{18}$c++代码

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    
    return true;
}

bool canFindPrime(int a, int b) {
    if (a == b) {
        return true;
    }
    
    int diff = abs(a - b);
    
    if (diff == 1) {
        return false;
    }
    
    if (isPrime(diff)) {
        return true;
    }
    
    return false;
}

int main() {
    int T;
    cin >> T;
    
    vector<pair<int, int>> testCases(T);
    for (int i = 0; i < T; i++) {
        cin >> testCases[i].first >> testCases[i].second;
    }
    
    for (int i = 0; i < T; i++) {
        if (canFindPrime(testCases[i].first, testCases[i].second)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

输入n个正整数，找出第k大的数C++

在C++中，要找出给定一组正整数中的第k大数，可以使用优先队列（堆数据结构）来实现。这里是一个基于这个思路的简单示例：

#include <iostream>
#include <queue>
using namespace std;

int findKthLargest(int arr[], int n, int k) {
    priority_queue<int, vector<int>, greater<int>> pq; // 使用最小堆

    for (int i = 0; i < n; ++i) {
        pq.push(arr[i]);
        
        if (pq.size() > k) {
            pq.pop(); // 如果堆元素超过k，弹出最小的
        }
    }

    // 当前堆顶就是第k大的数
    return pq.top();
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    
    cout << "The " << k << "th largest number is: " << findKthLargest(arr, n, k) << endl;
    return 0;
}

在这个程序中，我们首先创建了一个最小堆`pq`。遍历输入数组`arr`，将每个元素推入堆中。如果堆的大小超过了k，我们就弹出堆顶的元素，因为它是最小的。当所有元素都处理完后，堆顶元素即为第k大的数。