C++程序——按原始顺序查找最大的k个元素
给定一个数组arr[]和一个整数k,我们需要按输入顺序输出给定数组的前k个最大元素。
注意: k始终小于或等于n。
例子:
_{IDE} _
方法1: 我们在给定数组中搜索最大的元素k次。每次我们找到一个最大的元素,我们打印它并将其替换为数组中的负无穷大(C语言中的INT_MIN)。此方法的时间复杂度为O(n*k)。
输出
时间复杂度: O(n*k)
辅助空间: O(n)
方法2: 在此方法中,我们将原始数组存储在新数组中,并按降序对新数组进行排序。排序后,我们从0到n遍历原始数组,并打印所有出现在新数组的前k个元素中的元素。为了搜索,我们可以进行二进制搜索。
输出:
时间复杂度:对于排序,O(n Log n)。
辅助空间:O(n)
请参考完整文章以了解如何在原始顺序中找到k个最大元素!