哈尔滨网站制作哪里专业,网站建设维护有哪些内容,wordpress微信缩略图不显示,南昌做个网站多少钱目录 问题描述
解法及思想
第一种方式
算法思想
具体实现
第二种方式
算法思想
具体实现 问题描述
Top-K问题是一个十分经典的问题#xff0c;一般有以下两种方式来描述问题#xff1a;
在10亿的数字里#xff0c;找出其中最大的100个数#xff1b;在一个包含n个整…目录 问题描述
解法及思想
第一种方式
算法思想
具体实现
第二种方式
算法思想
具体实现 问题描述
Top-K问题是一个十分经典的问题一般有以下两种方式来描述问题
在10亿的数字里找出其中最大的100个数在一个包含n个整数的数组中找出最大的100个数。
前边两种问题描述稍有区别但都是说的Top-K问题前一种描述方式是说这里也许没有足够的空间存储大量的数字或其他东西我们最好可以在一边输入数据一边求出结果而不需要存储数据后一种说法则表示可以存储数据这种情况下最简单直观的想法就是对数组进行排序取后100个数即为所求。
解法及思想
第一种方式
这种情况下关键在于不能消耗太大的内存无法通过数组的简单排序来求取最大的K个数于是我们应该想到堆排序求最大的K个数就采用大小为K的最小二叉堆来实现我们知道二叉堆可以看作是一颗近似的完全二叉树其根节点正好就是K个数中最小的一个。
算法思想
先输入K个数建立一个大小为K的最小二叉堆接着每输入一个数与堆的根节点进行比较如果比根节点还小说明不可能为最大的K个数之一如果比根节点大那么替换根节点的值接着下沉根节点维护二叉堆的性质。这样到成功输入所有数据后最小二叉堆里剩下的就为最大的K个数。如果求最小的K个数同理换成最大二叉堆即可。
时间复杂度由于算法主要涉及对二叉堆结构的操作所以总体时间复杂度为O(nlgK)。
具体实现
/*
*代码采用STL中的最小优先队列实现由于STL中自带最小优先队列其底层就是二叉堆实现
*所以就不再手写二叉堆了。最小优先队列顶层元素总是队列中最小的元素也就是二叉堆堆顶。
*/#include iostream
#include queue
#include vector
using namespace std;/*由于STL自带优先队列是默认最大优先的所以自己写了一个比较函数将其改为最小优先*/
struct cmp1 {bool operator ()(int a, int b) {return ab; //最小值优先}
};int main() {//这里用来测试输入格式先输入需要求的最大K个数中的K值再依次输入数据流int K 0;cin K;int tmp 0;int i 0;priority_queueint,vectorint,cmp1 minHeap; //建立最小优先队列while (cin tmp) { //循环输入数据流if (i K) { //先建立一个K个大小的优先队列也就是K大小的二叉堆minHeap.push(tmp);}else { //算法实现if (tmp minHeap.top())continue;else if (tmp minHeap.top()) {minHeap.pop();minHeap.push(tmp);}}i;}while (!minHeap.empty()) { //输出最大的K个数cout minHeap.top() endl;minHeap.pop();}return 0;
}
第二种方式
这种情况由于可以操作存储数据的数组所以我们采用排序的方式进行求解但一般的排序时间复杂度也挺高题目只求最大的K个数不需要完全排序于是我们想到可以借用快排思想来进行求解。
算法思想
我们知道每运行一次Partition函数都会确定一个数m的最终位置且小于m的数均在其左边大于m的数都在其右边所以我们的目的就是当数m的右边正好有K-1个数的时候停止算法得到答案。每次运行Partition函数时根据前边上述性质若
K右边数组长度那么要找的K个数一定在m右边对m右边的数组运行Partition函数K右边数组长度1那么正好找到最大的K个数为数m以及其右边数组停止算法其他情况最大的K个数不仅仅在m数右边数组中对m左边数组运行Partition函数。
时间复杂度与快排类似Quick Select同样也是不稳定的算法最坏情况下时间复杂度会达到O(n^2)但平均性能也与快排类似时间复杂度一般可认为为O(n)。
具体实现
#include iostream
#include vectorusing namespace std;void swap(vectorintarr, int l, int r)//元素交换函数
{int temp arr[l];arr[l] arr[r];arr[r] temp;
}int Partition(vectorintarr, int left, int right)
{int less left - 1;//选准左边界int more right;//右边界int temp arr[right];//选定基准位置while (left more){if (arr[left] temp){swap(arr, less, left);//当前元素小于基准元素左边界内扩}else if (arr[left] temp)//当前元素大于基准元素右边界内扩左边界不变{swap(arr, --more, left);}elseleft;}swap(arr, more, right);//最后一个基准位置交换return left;//如果存在元素相等情况返回相同元素两侧的边界索引
}int main() {cout 请输入K endl;int K 0; //测试部分输入需要求的K值大小然后再依次输入数组元素cin K;int tmp 0;vectorint vec {1,2,6,8,10,50,34,36,27,58,70,66};int size vec.size();if (size 0 || K size)return 0;if (size K){for (int i 0; i size; i) { //测试部分输出需要求的K个数cout vec[i] endl;}}int left 0;int right vec.size() - 1;int index Partition(vec, left, right);while (index ! size - K) { //当Partition返回值及右边部分不是K大小时继续循环int sizeOfRight size - index - 1; //记录index右边数组长度大小if (K sizeOfRight) {index Partition(vec, index 1, right);}else if (K sizeOfRight 1) //这一步好像有点多余while循环保证了这点但为了对应博客文字描述就加上了continue;else if (K sizeOfRight 1) {index Partition(vec, left, index - 1);}}cout 输出TOPK个元素 endl;for (int i index; i size; i) { //测试部分输出需要求的K个数cout vec[i] ;}cout endl;return 0;
}
