首页 > C++的STL 堆 实现获取数组堆第K大的数

C++的STL 堆 实现获取数组堆第K大的数

前言

堆数据结构 使用的是优先级队列实现，创建堆的时候需要指定堆中元素的排列方式，即最大堆或者最小堆

最大堆即 堆顶元素为堆中最大的元素

最小堆即 堆顶元素为堆中最小堆元素

如下为一个最大堆

在这里插入图片描述

回到文章标题，获取一个数组中第K大的数，要求时间复杂度是O(n)，即一次遍历即可获取到该值。

所以普通的先排序，再获取第k个数值的方式显然不满足要求，排序最快的快速排序也需要O(log2 n)

这里就是我们前言中提到的堆 数据结构堆优势了，可以构建一个最小堆，堆顶始终为堆中所有元素的最小值。当然在本次实现中，仅需要将堆堆大小限制为要求的K个即可，此时遍历完数组的元素，堆顶即为数组中第K大的值。

基本过程如下图：

在这里插入图片描述

实现如下(文末有测试代码)：

int calculte_k_maxnum(vector<int> &arr, int k) { priority_queue <int,vector<int>, greater<int>> small_heap;//有衔接队列构建最小堆if (arr.empty()) { print_erro("the array is empty
",__LINE__);}/*按照步骤入堆*/for(int i =0;i < arr.size(); ++i) { if (small_heap.size() < k) { small_heap.push(arr[i]);} else if (small_heap.size() == k && small_heap.top() < arr[i]) { small_heap.pop();small_heap.push(arr[i]);}}/*最终的堆顶元素即为第K大的元素*/return small_heap.top();
}

测试代码如下：

#include 
#include 
#include using namespace std;void print_erro(string s,int line) { cout << s <<" " << line << endl;exit(-1);
}int calculte_k_maxnum(vector<int> &arr, int k) { priority_queue <int,vector<int>, greater<int>> small_heap;if (arr.empty()) { print_erro("the array is empty
",__LINE__);}for(int i =0;i < arr.size(); ++i) { if (small_heap.size() < k) { small_heap.push(arr[i]);} else if (small_heap.size() == k && small_heap.top() < arr[i]) { small_heap.pop();small_heap.push(arr[i]);}}return small_heap.top();
}int main(){ vector<int> arr;int k;int tmp;cout << "input the number of arr you want to get max " << endl;cin >> k;cout << "input the arr number " << endl;for (int i = 0;i < 5; ++i) { cin >> tmp;arr.push_back(tmp);}cout << "the k's max number of arr is " << calculte_k_maxnum(arr,k) << endl;return 0;
}

输出如下:

input the number of arr you want to get max 
4
input the arr number 
2 4 3 6 7
the k's max number of arr is 3input the number of arr you want to get max 
1        
input the arr number 
1 4 7 9 6
the k's max number of arr is 9

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 剑指offer: 面试题40. 最小的k个数

    题目：最小的k个数 入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0...

  • JS如何深度复制对象和数组，避免指针变量引用修改值

    //自定义深度复制对象or数组的递归方法---------------------------------------- let copyObjOrArr = o => {let isArray = o instanceof Array;let isObject = o instanceof Object;if (!isObject)...

  • 【数组方法大合集】原生js数组array常用工具方法大合集

    var array = {/* 数组求和*/sum: arr => eval(arr.join("+")),/* 判断一个数组(支持一个字符串)里面的是否有任何一个元素被包含在了某个字符串里面 */isStringContain(str, arr) {Array.isArray(arr) || (arr = [arr]);for (v...

  • 快速排序的两种实现方法(c语言版本)

    经过调研发现，对任意无序整数数组，快速排序有两种实现方法，这里简单阐述下思路： 思路一：随意选择一个基准元，一般选择数组的起始元或末尾元，Weiss这本书上特意搞了个算法来选择基准元，……，总之就是基准元的选择要尽量随机。选定基准元之后，比如选择数组起始元为基准元，从数组右边开始，向左边遍历，遇到比基准元大的跳过，直至遇到比基准元小...

  • 十种经典排序算法精粹(c语言版本)

    下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本，即下面的排序算法： 插入排序，shell排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，桶排序，基数排序和计数排序。整理出来以作备忘，不足之处，欢迎大家批评指正！其中计数排序分别给出了不稳定和稳定两种排序算法，测试时，使用随机生成大数组和随机手动输入的方法来测试。...

©2024 11GX.COM