C++程序——按原始顺序查找最大的k个元素

给定一个数组arr[]和一个整数k，我们需要按输入顺序输出给定数组的前k个最大元素。
注意: k始终小于或等于n。

例子：

输入：arr [] = {10 50 30 60 15}
        k = 2
输出：50 60
根据它们在原始数组中的出现顺序打印前2个元素。
输入：arr [] = {50 8 45 12 25 40 84}
        k = 3
输出：50 45 84

_{IDE} _

方法1： 我们在给定数组中搜索最大的元素k次。每次我们找到一个最大的元素，我们打印它并将其替换为数组中的负无穷大（C语言中的INT_MIN）。此方法的时间复杂度为O(n*k)。

// C++程序 - 查找k个最大元素
#include <bits/stdc++.h>
using namespace std;
 
// 打印k个最大元素的函数
void printMax(int a[], int n, int k)
{
    int b[n],c[n];
     
    // 将数组a复制到c中，并将数组b中
    // 的元素初始化为0。
    for(int i=0;i<n;i++)
    {
        c[i]=a[i];
        b[i]=0;
    }
     
    // 迭代k次以找到前k个最大元素
    for(int i=0;i<k;i++)
    {
        // 找到最大的元素和它的索引
        int maxi=INT_MIN;
        int index;
        for(int j=0;j<n;j++)
        {
            if(a[j]>maxi)
            {
                maxi=a[j];
                index=j;
            }
        }
        // 按顺序将1分配到k个最大数字的位置
        b[index]=1;
        a[index]=INT_MIN;
    }
     
    for(int i=0;i<n;i++)
    {
        // 打印数组中的k个最大元素
        if(b[i]==1)
        cout<<c[i]<<" ";
    }
}
 
// 驱动程序
int main()
{
    int a[] = { 50, 8, 45, 12, 25, 40, 84 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;
    printMax(a, n, k);
    return 0;
}
 
// 本代码由Aman kumar贡献。```

输出

50 45 84

时间复杂度： O(n*k)
辅助空间： O(n)

方法2： 在此方法中，我们将原始数组存储在新数组中，并按降序对新数组进行排序。排序后，我们从0到n遍历原始数组，并打印所有出现在新数组的前k个元素中的元素。为了搜索，我们可以进行二进制搜索。

// C++程序——按原始顺序查找k个最大元素
#include <bits/stdc++.h>
using namespace std;
 
// 打印m个最大元素的函数
void printMax(int arr[], int k, int n)
{
    // 向量存储原数组的拷贝
    vector<int> brr(arr, arr + n);
 
    // 按降序对向量排序。请参见以下链接
    // 的详情
    // https://www.geeksforgeeks.org/sort-c-stl/
    sort(brr.begin(), brr.end(), greater<int>());
 
    // 遍历原数组并打印所有
    // 出现在排序向量的前k个元素中的元素
    // 请参见 https://goo.gl/44Rwgt
    // 关于二进制搜索的详细信息()
    for (int i = 0; i < n; ++i)
        if (binary_search(brr.begin(),
                 brr.begin() + k, arr[i],
                        greater<int>()))
            cout << arr[i] << " ";
}
 
// 驱动程序
int main()
{
    int arr[] = { 50, 8, 45, 12, 25, 40, 84 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    printMax(arr, k, n);
    return 0;
}

输出：