首页 > 代码库 > 编程之美2.5 寻找最大的K个数
编程之美2.5 寻找最大的K个数
在一个数组中寻找最大的K个数,我们首先说一种非常简单的方法,利用快速排序中的分割算法,即我们经常看见的partition。这个函数会返回一个 int 类型的值,这个值代表的是前一半数字和后一半数字的分割点,前一半数字都小于等于后一半数字(递增排序),所以,我们只要找到相对应的分割点,即可以找到最大的K个数,或者最小的K个数,这就是利用线性方法可以完成任务的方法。
首先,给出函数声明:
int DutPartition(int*, int, int); void DutFindMaxKInArray_1(int*, int, int);
源代码如下:
/*经典的快排分割程序*/ int DutPartition(int* A, int low, int high) { /*哨兵,这里其实也可以用rand生成一个随机值,避免效率最低化*/ int pivot = A[low]; while (low < high) { while (low < high && A[high] >= pivot) --high; A[low] = A[high]; while (low < high && A[low] <= pivot) ++low; A[high] = A[low]; } A[low] = pivot; /*最终返回“中点”位置*/ return low; } /*这里的解法很简单,就是一直寻找index的最终位置,找到了就可以跳出循环了*/ void DutFindMaxKInArray_1(int* A, int size, int k) { if (!A || size <= 0 || k < 1 || size < k) return; int index = DutPartition(A, 0, size - 1); /*寻找最终位置*/ while (index != size - k) { if (index < size - k) index = DutPartition(A, index + 1, size - 1); else index = DutPartition(A, 0, index - 1); } /*输出最大的K个值*/ for (int i = size - k; i < size; ++i) cout << A[i] << " "; cout << endl; }
经过分析代码,我们可以知道,这个方法会改变原来数组中数字的顺序。假如说,不允许改变原来的结构呢?那么,我们可以利用最小堆解决TOPK的问题,最小堆的性质是堆顶元素是堆中元素值最小的一个,所以,我们只要判断下当前的堆顶元素是否比数组中元素小就可以了,如果是小,那么替换并重新调整堆,如果是大,那么不用理会这个元素。
由于 stl 中 multiset 是利用红黑树实现的,可以实现堆的性质,所以,我们可以利用 multiset 来解决这个问题,这种方法得到的时间复杂度是O(nlogn)
函数声明如下:
/*2.5 寻找最大的K个数*/ typedef std :: multiset<int, std :: less<int>> intSet; typedef std :: multiset<int, std :: less<int>> :: iterator setInterator; void DutFindMaxKInArray_2(const std :: vector<int>&, intSet&, int);
源代码如下:
/*第一种解法不好的地方在于它改变了数组中原来数的顺序*/ /* *第二种解法利用最小堆的思想寻找TOPK,是经典的大数据解题方法, *网络上很多类似的解释,这里,不做过多的解释 */ void DutFindMaxKInArray_2(const std :: vector<int>& data, /*模拟最小堆*/intSet& leastNums, int k) { leastNums.clear(); if (k < 1 || data.size() < k) return; vector<int> :: const_iterator iter = data.begin(); for (; iter != data.end(); ++iter) { if (leastNums.size() < k) { leastNums.insert(*iter); } else { setInterator it = leastNums.begin(); if (*iter > *it) { leastNums.erase(it); leastNums.insert(*iter); } } } }
编程之美2.5 寻找最大的K个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。