• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

top-k算法的二分实现(修正版)(C++实现)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

摘要:本文简要介绍了top-k(求一个序列中前K个最大或最小的元素)算法的二分实现方法,并给出了C++源

代码

关键字:top-k,二分,快排序

网上介绍top-k算法的博文貌似不多,有一个搜索引擎中排名靠前的top-k算法介绍中给出了源码,

我试了试,发现有点小BUG,就自己整理了一下,先说说实现原理,后面给出源码。

top-k的实现方法比较常见的有堆和二分法,这里只介绍二分实现方法,具体思路如下:

以求长度为N的整数数组中前K个最大数为例,类似于快排序,本方法递归地把数组分为两部分

(设划分点索引为M),将大的数放到左边部分,将小的数放到右边部分。如果M大于K

对数组0~(M-1)部分执行top-k算法;如果M小于等于K,计上一次划分点索引为LAST, 对数组0~LAST

进行快排序。运行结束后,数组的0~(K-1)即为最大的K个整数!算法的时间复杂度为O(N*log2K),适合

数据可以全部装入内存的情形!

源码如下(VC++ 6.0编译测试通过):


/*
 * 二分实现top-k算法
 * 取长度为N的整数数组中前K个最大的数
 */

#include <iostream>
#include <ctime>
using namespace std;

#define MAX_NUM 1000

#define N 200

#define K 20

/* global data */

int array[N];

/* funcitons declaration*/
void init_array(int n);
void print_result(int n);
void quicksort(int low, int high);
void topk(int low, int high, int k);

/* main */

int main(int argc, char* *argv)
{
        cout<<"init array,size:"<<N<<"......"<<endl;
        init_array(N);
        print_result(N);
        cout<<"generate top-"<<K<<"......"<<endl;
        topk(0, N - 1, K);
        cout<<"result....."<<endl;
        print_result(K);
        system("pause");
        return 0;
}

/* function definition */

void init_array(int n)
{
        for(int i = 0; i < n; ++i)
        {
                array[i] = rand() % MAX_NUM;
        }
}

void print_result(int n)
{
        for(int i = 0; i < n; ++i)
        {
                cout<<array[i]<<" ";
        }
        cout<<endl;
}
       
void mswap(int i, int j)
{
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
}
void quicksort(int low, int high)
{
        if(low >= high) return;
        mswap(low, rand() % (high - low + 1) + low);
        int m = low;
        for(int i = low + 1; i <= high; ++i)
        {
                if(array[i] > array[low])
                {
                        mswap(++m, i);
                }
        }
        mswap(m, low);
        quicksort(low, m - 1);
        quicksort(m + 1, high);
}

void topk(int low, int high, int k)
{
        static int last = high;
        if(low >= high) return;
        mswap(low, rand() % (high - low + 1) + low);
        int m = low;
        for(int i = low + 1; i <= high; ++i)
        {
                if(array[i] > array[low])
                {
                        mswap(++m, i);
                }
        }
        mswap(m, low);
        if(k < m)
        {
                last = m;
                topk(low, m - 1, k);
        }
        else
        {
                quicksort(low, last);
        }
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
大整数乘法(高精度乘法)的实现源码(原创)发布时间:2022-05-14
下一篇:
最小生成树算法(一)之Prim算法(C++实现)发布时间:2022-05-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap