C++ 实现数组降序排序后取前 30% 最小值

C++ 实现数组降序排序后取前 30% 最小值

本文将介绍如何使用 C++ 实现对数组进行降序排序后，获取前 30% 元素中的最小值。

代码示例

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

const int MAXN = 100000;
int a[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n, greater<int>()); //按降序排序
    int k = n / 10; //前30%的个数
    int ans = a[k - 1]; //第k个数即为前30%中最小的数
    cout << ans << endl;
    return 0;
}

思路解析

1. 输入数组。
2. 使用 STL 中的 sort 函数进行降序排序，sort 函数默认是升序排序，需要用 greater<int> 作为第三个参数指定降序排序。
3. 计算前 30% 的个数 k，即 n/10。
4. 数组下标从 0 开始，第 k 个数的下标为 k-1，输出即可。

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

总结

本文通过 C++ 代码示例，展示了如何对数组进行降序排序并获取前 30% 元素中的最小值。代码简洁易懂，并附有详细的思路解析和复杂度分析。希望对您理解和掌握相关算法有所帮助。