TOP K问题解法整理（C++实现）

2024-07-14 03:11| 来源: 网络整理| 查看: 265

文章目录前言一、top K问题是什么？二、解法1.基础中的基础解法2.进阶一：局部冒泡3.进阶二：快速选择3.进阶三：构造小顶堆/大顶堆总结

前言

本文记录了针对各厂面试中常出的TOP K问题（求最大/最小的第K个元素）的各种解法。限于笔者实力不足，本文仅罗列笔者能够手写出的算法实现（欢迎补充）

一、top K问题是什么？

在一堆数据里面找到前 K大/小的数。常见面试题出法：最大（小）K个数，前K个高频元素，第K个最大（小）元素。具体有：有整数数组 a[8] = {4，5，1，6，2，7，3，8}这8个数字，则前4（K）大的数字为8，7，6，5这几个数字。

二、解法 1.基础中的基础解法

要找前K大或者前K小的数，首先想到的方法就是将所有数据整体进行一个排序，然后输出前K个或者后K个（前n-K）个数据。代码如下（示例）：

#include #include #include using namespace std; void QuickSort(vector &v, int start, int end) { int i = start; int j = end; if (i

【本文地址】

今日新闻