精华内容
下载资源
问答
  • topk问题
    千次阅读
    2019-08-09 14:22:26

    内容

    一、排序

    二、局部排序

    三、堆

    四、随机选择

    为各个算法添加了C++ 实现代码


    面试中,TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。

    画外音:除非校招,我在面试过程中从不问TopK这个问题,默认大家都知道。

    问题描述:

    从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。

    栗子:

    从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。

    一、排序

    排序是最容易想到的方法,将n个数排序之后,取出最大的k个,即为所得。

    伪代码:

    sort(arr, 1, n);

    return arr[1, k];

    C++ 代码:

        /**
         * 方法1 排序后取前K个数字 时间复杂度O(n*log(n)) 运行时间:4ms 占用内存:504k
         * @param input vector
         * @param k int
         * @return 
         */
        vector<int> GetLeastNumbers_Solution1(vector<int> input, int k) {
            vector<int> ans;
            if (k > input.size() || input.size() == 0 || k == 0) {
                return ans;
            }
            sort(input.begin(), input.end());
            for (int i = 0; i < k; i++) {
                ans.push_back(input[i]);
            }
            return ans;
        }

    时间复杂度:O(n*lg(n))


    分析:明明只需要TopK,却将全局都排序了,这也是这个方法复杂度非常高的原因。那能不能不全局排序,而只局部排序呢?这就引出了第二个优化方法。

    二、局部排序

    不再全局排序,只对最大的k个排序。

    冒泡是一个很常见的排序方法,每冒一个泡,找出最大值,冒k个泡,就得到TopK。

     

    伪代码:

    for(i=1 to k){

             bubble_find_max(arr,i);

    }

    return arr[1, k];

    C++代码:

        /**
         * 方法2 冒泡法, 每次取一个最小值, 时间复杂度O(n*k) 运行时间:4ms占用内存:468k
         * @param input 
         * @param k 
         * @return 
         */
        vector<int> GetLeastNumbers_Solution2(vector<int> input, int k) {
            vector<int> ans;
            if (k > input.size() || input.size() == 0 || k == 0) {
                return ans;
            }
            BubbleSort(input, k);
            for (int i = 0; i < k; i++) {
                ans.push_back(input[i]);
            }
            return ans;
        }
        /**
         * 冒泡排序算法,只得到前k个最小值
         * @param input
         * @param k
         */
        void BubbleSort(vector<int> &input, int k) {
            for (int i = 0; i < k; i++) {
                int temp_i = i;
                int count = input.size() - 1;
                while (count - 1 >= temp_i) {
                    if (input[count] < input[count - 1]) {
                        int t = input[count - 1];
                        input[count - 1] = input[count];
                        input[count] = t;
                    }
                    count -= 1;
                }
            }
        }

    时间复杂度:O(n*k)

     

    分析:冒泡,将全局排序优化为了局部排序,非TopK的元素是不需要排序的,节省了计算资源。不少朋友会想到,需求是TopK,是不是这最大的k个元素也不需要排序呢?这就引出了第三个优化方法。

     

    三、堆

    思路:只找到TopK,不排序TopK。

    先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。

     

    接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。

     

    直到,扫描完所有n-k个元素,最终堆中的k个元素,就是猥琐求的TopK。

     

    伪代码:

    heap[k] = make_heap(arr[1, k]);

    for(i=k+1 to n){

             adjust_heap(heep[k],arr[i]);

    }

    return heap[k];

    C++ 代码:

        /**
         * 建立最大堆
         * @param input
         * @param heap
         * @param k heap size
         */
        void BuildMaxHeap(vector<int> &input, vector<int> &heap, int k) {
            for (int i = 0; i < k; i++) {
                heap.push_back(input[i]);
            }
            sort(heap.begin(), heap.end());
            reverse(heap.begin(), heap.end());
        }
    
        /**
         * 把heap堆顶的值下沉到合适的位置
         * @param heap
         */
        void ShiftMaxDown(vector<int> &heap) {
            int cur_root = 0;
            int cur_left = 2 * cur_root + 1;
            int cur_right = 2 * cur_root + 2;
            while (true) {
                if (cur_left < heap.size() && heap[cur_root] < heap[cur_left]) {
                    int temp = heap[cur_root];
                    heap[cur_root] = heap[cur_left];
                    heap[cur_left] = temp;
                    cur_root = cur_left;
                    cur_left = 2 * cur_root + 1;
                    cur_right = 2 * cur_root + 2;
                } else if (cur_right < heap.size() && heap[cur_root] < heap[cur_right]) {
                    int temp = heap[cur_root];
                    heap[cur_root] = heap[cur_right];
                    heap[cur_right] = temp;
                    cur_root = cur_right;
                    cur_left = 2 * cur_root + 1;
                    cur_right = 2 * cur_root + 2;
                } else {
                    break;
                }
            }
        }
        /**
         * 方法3 维护一个大小为K的最大堆(如果是求最大的K个数,则为最小堆), 时间复杂度O(n*log(k)), 运行时间:3ms占用内存:480k
         * 该方法可以处理规模更大的数据(但是需要K较小,会有比较高的效率),比如在内存中放不下,只能通过硬盘顺序读取.
         * @param input 
         * @param k 
         * @return 
         */
        vector<int> GetLeastNumbers_Solution3(vector<int> input, int k) {
            vector<int> ans;
            if (k > input.size() || input.size() == 0 || k == 0) {
                return ans;
            }
            BuildMaxHeap(input, ans, k);
            for (int i = k; i < input.size(); i++) {
                if (ans[0] > input[i]) {
                    ans[0] = input[i];
                    ShiftMaxDown(ans);
                }
            }
            return ans;
        }

    时间复杂度:O(n*lg(k))

    画外音:n个元素扫一遍,假设运气很差,每次都入堆调整,调整时间复杂度为堆的高度,即lg(k),故整体时间复杂度是n*lg(k)。

     

    分析:堆,将冒泡的TopK排序优化为了TopK不排序,节省了计算资源。堆,是求TopK的经典算法,那还有没有更快的方案呢?

     

    四、随机选择

    随机选择算在是《算法导论》中一个经典的算法,其时间复杂度为O(n),是一个线性复杂度的方法。

     

    这个方法并不是所有同学都知道,为了将算法讲透,先聊一些前序知识,一个所有程序员都应该烂熟于胸的经典算法:快速排序。

    画外音:

    (1)如果有朋友说,“不知道快速排序,也不妨碍我写业务代码呀”…额...

    (2)除非校招,我在面试过程中从不问快速排序,默认所有工程师都知道;

     

    其伪代码是:

    void quick_sort(int[]arr, int low, inthigh){

             if(low== high) return;

             int i = partition(arr, low, high);

             quick_sort(arr, low, i-1);

             quick_sort(arr, i+1, high);

    }

     

    其核心算法思想是,分治法。

     

    分治法(Divide&Conquer),把一个大的问题,转化为若干个子问题(Divide),每个子问题“都”解决,大的问题便随之解决(Conquer)。这里的关键词是“都”。从伪代码里可以看到,快速排序递归时,先通过partition把数组分隔为两个部分,两个部分“都”要再次递归。

     

    分治法有一个特例,叫减治法。

     

    减治法(Reduce&Conquer),把一个大的问题,转化为若干个子问题(Reduce),这些子问题中“只”解决一个,大的问题便随之解决(Conquer)。这里的关键词是“只”。

     

    二分查找binary_search,BS,是一个典型的运用减治法思想的算法,其伪代码是:

    int BS(int[]arr, int low, inthigh, int target){

             if(low> high) return -1;

             mid= (low+high)/2;

             if(arr[mid]== target) return mid;

             if(arr[mid]> target)

                       return BS(arr, low, mid-1, target);

             else

                       return BS(arr, mid+1, high, target);

    }

     

    从伪代码可以看到,二分查找,一个大的问题,可以用一个mid元素,分成左半区,右半区两个子问题。而左右两个子问题,只需要解决其中一个,递归一次,就能够解决二分查找全局的问题。

     

    通过分治法与减治法的描述,可以发现,分治法的复杂度一般来说是大于减治法的:

    快速排序:O(n*lg(n))

    二分查找:O(lg(n))

     

    话题收回来,快速排序的核心是:

    i = partition(arr, low, high);

     

    这个partition是干嘛的呢?

    顾名思义,partition会把整体分为两个部分。

    更具体的,会用数组arr中的一个元素(默认是第一个元素t=arr[low])为划分依据,将数据arr[low, high]划分成左右两个子数组:

    左半部分,都比t大

    右半部分,都比t小

    中间位置i是划分元素

    以上述TopK的数组为例,先用第一个元素t=arr[low]为划分依据,扫描一遍数组,把数组分成了两个半区:

    左半区比t大

    右半区比t小

    中间是t

    partition返回的是t最终的位置i。

     

    很容易知道,partition的时间复杂度是O(n)。

    画外音:把整个数组扫一遍,比t大的放左边,比t小的放右边,最后t放在中间N[i]。

     

    partition和TopK问题有什么关系呢?

    TopK是希望求出arr[1,n]中最大的k个数,那如果找到了第k大的数,做一次partition,不就一次性找到最大的k个数了么?

    画外音:即partition后左半区的k个数。

     

    问题变成了arr[1, n]中找到第k大的数。

     

    再回过头来看看第一次partition,划分之后:

    i = partition(arr, 1, n);

    如果i大于k,则说明arr[i]左边的元素都大于k,于是只递归arr[1, i-1]里第k大的元素即可;

    如果i小于k,则说明说明第k大的元素在arr[i]的右边,于是只递归arr[i+1, n]里第k-i大的元素即可;

    画外音:这一段非常重要,多读几遍。

    这就是随机选择算法randomized_select,RS,其伪代码如下:

    int RS(arr, low, high, k){

      if(low== high) return arr[low];

      i= partition(arr, low, high);

      temp= i-low; //数组前半部分元素个数

      if(temp>=k)

          return RS(arr, low, i-1, k); //求前半部分第k大

      else

          return RS(arr, i+1, high, k-i); //求后半部分第k-i大

    }

    C++ 代码:

        /**
         * quick sort core
         * @param input 
         * @param start 
         * @param end 
         * @return 
         */
        int Partition(vector<int> &input, int start, int end) {
            int temp = input[start];
            while (start < end) {
                while (start < end && temp <= input[end]) {
                    end -= 1;
                }
                input[start] = input[end];
                if (start < end) {
                    start += 1;
                    while (start < end && temp > input[start]) {
                        start += 1;
                    }
                    input[end] = input[start];
                    end -= 1;
                }
            }
            input[start] = temp;
            return start;
        }
    
        /**
         *方法4 基于快排的方法,一次定位到key之后,如果key的index + 1==K,那么这前K个刚好就是要求最小的值, 复杂度O(n), 运行时间:3ms 占用内存:480k
         *如果key的index+1> K则继续递归前半部分即可,如果key的index+1<K,只需要递归后半部分
         * @param input
         * @param k
         * @return
         */
        vector<int> GetLeastNumbers_Solution4(vector<int> input, int k) {
            vector<int> ans;
            if (k > input.size() || input.size() == 0 || k == 0) {
                return ans;
            }
            int start = 0;
            int end = input.size() - 1;
            int part_index = Partition(input, 0, input.size() - 1);
            while (part_index + 1 != k) {
                if (part_index + 1 > k) {
                    end = part_index - 1;
                    part_index = Partition(input, start, end);
                } else {
                    start = part_index + 1;
                    part_index = Partition(input, start, end);
                }
            }
            for (int i = 0; i < k; i++) {
                ans.push_back(input[i]);
            }
            return ans;
        }

    这是一个典型的减治算法,递归内的两个分支,最终只会执行一个,它的时间复杂度是O(n)。

     

    再次强调一下:

    分治法,大问题分解为小问题,小问题都要递归各个分支,例如:快速排序

    减治法,大问题分解为小问题,小问题只要递归一个分支,例如:二分查找,随机选择

     

    通过随机选择(randomized_select),找到arr[1, n]中第k大的数,再进行一次partition,就能得到TopK的结果。

     

    五、总结

    TopK,不难;其思路优化过程,不简单:

    全局排序,O(n*lg(n))

    局部排序,只排序TopK个数,O(n*k)

    堆,TopK个数也不排序了,O(n*lg(k))

    分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n))

    减治法,“只要”递归一个分支,例如:二分查找O(lg(n)),随机选择O(n)

    TopK的另一个解法:随机选择+partition

     

    知其然,知其所以然。

    思路比结论重要。

    希望大家对TopK有新的认识,谢转。
    原文链接:https://blog.csdn.net/z50L2O08e2u4afToR9A/article/details/82837278

    更多相关内容
  • topk 问题,就是从一个数组或者列表中获取最大的K个数,求3个积分,因为我需要3个积分下载东西,但是,我的里面的topK 解决方案肯定是比较全的,如果有什么看不懂的,请联系我,绝对负责给你讲清楚
  • Topk问题的三种求解方法

    千次阅读 多人点赞 2021-09-02 16:40:52
    Topk问题的三种求解方法什么是Topk问题方法一:堆排序法方法二:把N个数建堆,取出前k个方法三:建一个k个数的堆 什么是Topk问题 其实顾名思义,这个问题也就是在N个数中找出前k个最值。在我们的日常生活中,很多...

    什么是Topk问题

    其实顾名思义,这个问题也就是在N个数中找出前k个最值。在我们的日常生活中,很多地方都有Topk问题的影子,例如我们在点外卖时,总会说这家店是某某市的多少名,其实这些都是用Topk问题的解决方法得出来的。

    方法一:堆排序法

    这也是最容易想到的一种方法:我们可以将N个数排成有序的,然后输出前k个最值,而在我们已学过的排序算法中,堆排序的时间复杂度又是最快的(O(n*logn)),因此我们选择了堆排序。

    //交换函数
    void Swap(int* x, int* y)
    {
    	int tmp = *x;
    	*x = *y;
    	*y = tmp;
    }
    //堆的向下调整(小堆)
    void AdjustDown(int* a, int n, int parent)
    {
    	//child记录左右孩子中值较小的孩子的下标
    	int child = 2 * parent + 1;//先默认其左孩子的值较小
    	while (child < n)
    	{
    		if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
    		{
    			child++;//较小的孩子改为右孩子
    		}
    		if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
    		{
    			//将父结点与较小的子结点交换
    			Swap(&a[child], &a[parent]);
    			//继续向下进行调整
    			parent = child;
    			child = 2 * parent + 1;
    		}
    		else//已成堆
    		{
    			break;
    		}
    	}
    }
    int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
    {
    	*returnSize = k;
    	int i = 0;
    	//建小堆
    	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(arr, arrSize, i);
    	}
    	//排降序
    	int end = arrSize - 1;
    	while (end > 0)
    	{
    		Swap(&arr[0], &arr[end]);
    		AdjustDown(arr, end, 0);
    		end--;
    	}
    	//将最大的k个数存入数组
    	int* retArr = (int*)malloc(sizeof(int)*k);
    	for (i = 0; i < k; i++)
    	{
    		retArr[i] = arr[i];
    	}
    	return retArr;//返回最大的k个数
    }
    
    

    时间复杂度:O(N+NlogN) 空间复杂度:O(N),能否将其再优化了?肯定是可以的,下面看方法二。

    方法二:把N个数建堆,取出前k个

    这种方法其实也不难想到,我们利用了堆的性质:堆的0号位一定是最值,小堆则为最小值,大堆则为最大值。

    注意点:
    1.取出数据后要让其与最后的元素替换,因为你已经取出这个元素了,所以不需要它了,这时让它去堆尾,不让它算入堆的个数中就行了。为什么要这样做了,因为这样既保证了堆的结构,也相当于把这个取出来的数删除了
    2. 如果在取到堆顶数据后直接删除数据,那么就要重新建堆了。正确的做法应该是上面所说的方法,因为那样只要进行一次向下调整,就可以保证堆的结构了。要知道建堆的复杂度为O(N),而一次向下调整的复杂度仅为O(logn),这样大大提升了效率。

    //交换函数
    void Swap(int* x, int* y)
    {
    	int tmp = *x;
    	*x = *y;
    	*y = tmp;
    }
    //堆的向下调整(大堆)
    void AdjustDown(int* a, int n, int parent)
    {
    	//child记录左右孩子中值较大的孩子的下标
    	int child = 2 * parent + 1;//先默认其左孩子的值较大
    	while (child < n)
    	{
    		if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大
    		{
    			child++;//较大的孩子改为右孩子
    		}
    		if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大
    		{
    			//将父结点与较大的子结点交换
    			Swap(&a[child], &a[parent]);
    			//继续向下进行调整
    			parent = child;
    			child = 2 * parent + 1;
    		}
    		else//已成堆
    		{
    			break;
    		}
    	}
    }
    int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
    {
    	*returnSize = k;
    	int i = 0;
    	//建大堆
    	for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(arr, arrSize, i);
    	}
    	//将最大的k个数存入数组
    	int* retArr = (int*)malloc(sizeof(int)*k);
    	int end = arrSize - 1;
    	for (i = 0; i < k; i++)
    	{
    		retArr[i] = arr[0];//取堆顶数据
    		Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据
    		//进行一次向下调整,不把最后一个数据看作待调整的数据,所以待调整数据为end=arrSize-1
    		AdjustDown(arr, end, 0);
    		end--;//最后一个数据的下标改变
    	}
    	return retArr;//返回最大的k个数
    }
    
    

    时间复杂度:O(n+k*logn),空间复杂度:O(n),那么问题来了,万一n是一个特别大的数字了,那效率依旧不是很高,有没有更快的方法了?下面我们来看看方法三。

    方法三:建一个k个数的堆

    我们以找出最大的k个数为例,该方法为:先建一个k个数的小堆,然后将数组中n-k个元素依次与堆顶的元素比较,若比堆顶元素大,则将堆顶元素删除,然后将这个数插入到堆中,这儿要注意:插入这个数到堆中的时候,要使用向上排序算法保证堆的结构不被破坏。到最后,堆里面的k个数就是最大的k个数了。

    那么问题来了,上面的例子中为什么不用大堆了,不是选最大的k个数吗?其实这很容易理解,我们假设一下,如果建一个大堆,万一堆顶的数据就是n个数中最大的那个,那么不论怎么比较,你后面的n-k个元素都没法进堆,因此要用小堆来解决这个问题。

    void PrintTopK(int* a, int n, int k)
    {
    	Hp hp;
    	HpInit(&hp, a, k);
    	int i = k;
    	for (i = k; i < n; i++)
    	{
    		if (a[i]>HpTop(hp))
    		{
    			HpPop(&hp);
    			HpPush(&hp, a[i]);
    		}
    	}
    	//你此时数据改变之后是在堆里面的,你打印a没用啊
    	//for (i = 0; i < k; i++)
    	//{
    	//	printf("%d ", a[i]);
    	//}
    	for (i = 0; i < k; i++)
    	{
    		printf("%d ", HpTop(hp));
    		HpPop(&hp);
    	}
    	printf("\n");
    }
    

    时间复杂度:O(k+n*logk) 空间复杂度:O(n) 与之前两种方法对比,这种方法大大提高了效率。

    展开全文
  • TopK问题的三种解法

    千次阅读 2021-03-19 14:12:31
    TopK问题是指从n个数据中取前K个数据,在生活中的应用也有很多,如游戏中xxx的排行榜前10名等。在这篇博客中我将主要利用堆去解决TopK问题。 堆排序 首先我们需要建一个堆,然后我们再进行堆排序,排好序后直接取...

    TopK问题是指从n个数据中取前K个数据,在生活中的应用也有很多,如游戏中xxx的排行榜前10名等。在这篇博客中我将主要利用去解决TopK问题。

    堆排序

    首先我们需要建一个堆,然后我们再进行堆排序,排好序后直接取前K个就可以了。需要注意的是在使用堆排序的时候,我们需要确定我们要排升序还是降序。如果是升序的话,我们要建一个大根堆;如果是降序的话,我们要建一个小根堆思路:(可以结合图来进行分析) 这里我们以排降序为例子进行说明,建好小根堆后,我们将堆顶元素与堆中的最后一个元素进行互换   (让最小的元素换到最后面,以此来达到降序),此时最后一个元素就是最小的那个元素了,然后让堆的大小 - 1,也就是我们将最后一个元素从堆中踢出,可以将它看做已排好序的一个集合。然后再对这个堆进行向下调整算法,重新让它成为一个小根堆,然后重复这段操作,直到堆中只剩1个元素。堆排序的时间复杂度为O(n*logn)。

    //向下调整算法
    void AdjustDown(int* a, int n, int root)
    {
    	int parent = root;
    	int child = 2 * parent + 1;
    
    	while (child < n)
    	{
    		//左孩子和右孩子进行比较,选出较小的【如果没有右孩子,不进行该比较】
    		if (child + 1 < n && a[child] > a[child + 1])
    		{
    			child++;
    		}
    		//判断孩子节点和父节点【调成小堆】
    		if (a[child] < a[parent])
    		{
    			int tmp = a[child];
    			a[child] = a[parent];
    			a[parent] = tmp;
    
    			parent = child;
    			child = 2 * child + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    void HeapCreate(Heap* hp, HpDataType* a, int sz)
    {
    	//堆的空间开辟和初始化
    	hp->_a = (HpDataType*)malloc(sizeof(HpDataType)*sz);
    	hp->_size = sz;
    	hp->_capacity = sz;
    	//数据的拷贝
    	memcpy(hp->_a, a, sizeof(HpDataType)*sz);
    
    	//堆的创建
    	int i = 0;
    	for (i = (sz - 1 - 1) / 2;i >= 0;--i)
    	{
    		AdjustDown(hp->_a, sz, i);
    	}
    }
    
    void HeapSort(Heap* hp)
    {
    	int i = 0;
    	for (i = hp->_size - 1; i > 0;--i)
    	{
    		Swap(&hp->_a[i], &hp->_a[0]);
    		AdjustDown(hp->_a, i, 0);
    	}
    }
    
    void PrintTopK(int* a, int n, int K)
    {
    	Heap hp;
    	HeapCreate(&hp, a, K);
    	HeapSort(&hp);
    
    	int i = 0;
    	for (i = 0; i < K; ++i)
    	{
    		printf("%d ", hp._a[i]);
    	}
    }

    建一个大小为n的堆

    我们利用所给的n个数据去建一个大小为n的堆,如果求的是最大的K个数据,那么我们需要建大根堆;要求最小的K个数据,我们要建小根堆。这里我们以求最大的K个数据为例子,我们建一个大小为n的大根堆,然后这个堆的堆顶元素(HeapTop),然后再对将堆顶元素进行删除(HeapPop)的操作,然后再进行向下调整算法。要求最大的K个,那么只要循环K次即可。

    HpDataType HeapTop(Heap* hp)
    {
    	return hp->_a[0];
    }
    
    void HeapPop(Heap* hp)
    {
    	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    	hp->_size--;
        //每进行完1次删除,都要进行1次向下调整
    	AdjustDown(hp->_a, hp->_size, 0);
    }
    
    void PrintTopK(int* a, int n, int K)
    {
    	Heap hp;
    	HeapCreate(&hp, a, K);
    
    	int i = 0;
    	for (i = 0; i < K; ++i)
    	{
    		printf("%d ", HeapTop(&hp));
    		HeapPop(&hp);
    	}
    }
    

    建一个大小为K的堆

    这里我们以求最大的K个数据为例子。首先,我们先用一组数据中的前K个数据建一个小根堆,然后依次的用剩下的数据与小根堆的堆顶元素进行比较,如果该元素大于堆顶元素,那么将该元素替换为堆顶元素,随后再进行向下调整,使其保持小根堆,当所有元素都比较完后,小根堆中的K个元素就是这些数据中的最大的K个元素了。

    void PrintTopK(int* a, int n, int K)
    {
    	Heap hp;
        //用前K个元素去建一个小根堆
    	HeapCreate(&hp, a, K);
    
        //用剩下的元素与堆顶元素进行比较
    	int i = 0;
    	for (i = K; i < n; ++i)
    	{
    		if (a[i] > HeapTop(&hp))
    		{
    			hp._a[0] = a[i];//替换堆顶元素
     			AdjustDown(hp._a, K, 0);
    		}
    	}
    	for (i = 0; i < K;++i)
    	{
    		printf("%d ", hp._a[i]);
    	}
    }
    

     

    展开全文
  • 【数据结构】TopK问题

    千次阅读 多人点赞 2021-11-08 23:00:45
    TopK问题 gitee上有更详尽的代码:堆 + TopK代码 文章目录TopK问题一、问题分析1. 方法一2. 方法二3. 方法三二、TopK实现1. 前k个数的小堆2. n-k个数和根去比较3. 打印堆三、测试 topk问题就是取n个数据中,找...

    TopK问题

    gitee上有更详尽的代码:堆 + TopK代码



    topk问题就是取n个数据中,找出最大/最小前k个数

    一、问题分析

    1. 方法一

    n个数据进行排序,再取出前k个元素

    • 时间复杂度:O(N * logN)

    2. 方法二

    n个数据依次插入大堆,然后pop堆的根 k 次

    • 时间复杂度:O(N + k * logN)

    设有n个数据,有log2(n + 1)层,最坏的情况就是每个数据要向上调整k次


    3. 方法三

    如果n很大,内存中无法储存,插入堆和排序的方法都不行

    • 用前K个数建立一个K个数的小堆

    • 剩下的N-K个数,依次跟堆顶的数据进行比较如果比堆顶数据大,就替换堆顶的数据,再向下调整

    • 最后堆里面K个数就是最大的K个数

    原理:

    在方法二的基础上,大堆实现不了,但小堆却能很好的实现

    小堆的优点就是,根是堆中所有元素中最小的元素,我们建立一个小堆,可以存放k个数,后面n-k个数字再与之比较,这样就能把小数pop出来,把大数push进去

    可能会担心:

    • 如果小堆里正好都是我们想要的数怎么办?

      那与之比较的n-k的数肯定没有比根更大的数了

    • 如果这里小堆换成大堆?

      那可能根是最大的数字,没法操作了。小的话放进去,那如果不是前k个大的数字就进去了,乱套了

    时间复杂度:O(k + (n-k)*logk)


    二、TopK实现

    本篇在上一章:【数据结构】堆_Rinne’s blog-CSDN博客

    写了几个二叉树常用的插口

    gitee上有更详尽的代码:堆 + TopK代码

    1. 前k个数的小堆

    //定义和初始化堆
    Heap hp;
    HeapInit(&hp);
    
    int i = 0;
    //k个数的小堆
    for (i = 0; i < k; i++)
    {
    	//插入k个数据
    	HeapPush(&hp, a[i]);
    }
    

    2. n-k个数和根去比较

    在这里插入图片描述

    比它大,替换

    在这里插入图片描述

    向下调整

    在这里插入图片描述

    //k - n 个数与根作对比
    for (i = k; i < n; i++)
    {
    	if (a[i] > HeapTop(&hp))
    	{
    		hp.a[0] = a[i];
    		AdjustDown(hp.a, hp.size, 0);
    	}
    }
    
    

    3. 打印堆

    //打印堆
    void HeapPrint(Heap* hp, int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		printf("%d ", hp->a[i]);
    	}
    	printf("\n");
    }
    

    三、测试

    测试代码:

    这里用到了srand函数和time函数以及rand函数,用来生成随机数值

    更多有关随机数生成的详细知识可以参考文章:C语言随机数生成教程

    void TestTopk()
    {
    	//一共有20个数字
    	int n = 20;
    	int* a = (int*)malloc(sizeof(int) * n);
    	assert(a);
    
    	srand((unsigned int)time(NULL));
    	
    	for (int i = 0; i < n; ++i)
    	{
    		a[i] = rand() % 10;
    	}
    	// 再去设置5个比10大的数
    	a[5] = 10 + 1;
    	a[11] = 10 + 2;
    	a[15] = 10 + 3;
    	a[1] = 10 + 4;
    	a[10] = 10 + 5;
    
    	PrintTopK(a, n, 5);
    
    
    }
    

    测试结果:

    在这里插入图片描述


    下一篇会讲解堆排序的问题,可能感觉和topk相似,但topk只是找了前k个大的数,并没有排序

    展开全文
  • topk问题的Python实现,k-堆实现
  • Top K 问题的解决方案

    万次阅读 多人点赞 2019-01-10 16:39:23
    Top K是很常见的一种问题,是指在N个数的无序序列中找出最大的K个数,而其中的N往往都特别大,对于这种问题,最容易想到的办法当然就是先对其进行排序,然后直接取出最大的K的元素就行了,但是...
  • Top K问题(3种解法)

    千次阅读 2020-06-04 22:19:39
    Top K问题 找到数组中最大(最小)的K个数,例如7,6,3,5,2,Top3 的意思就是 找出最小的三个数即为:3,5,2. 解法1 讲数组从小到大进行排序,然后取出前K个数。 (先说最差的一个,为了引出后面的优化解法打铺垫) ...
  • 一、基础知识 1.1 什么是最大(小)堆 最大堆,最小堆类似,以下以最小堆为例进行讲解。...1.3 什么是TOP K问题 Top K指的是从n(很大)个数据中,选取最大(小)的k个数据。例如学校要从全校学...
  • 两个有序数组间相加和的Top k问题

    千次阅读 2018-04-23 13:52:03
    import java.util.*;...//两个有序数组间相加和的Top k问题 public class FindArrTopK{ //堆节点的定义 public static class HeapNode{ public int row; public int col; public int value; ...
  • 在面试中面试官经常会问这样一个问题:现在有N个数,请找出最大的或最小的前k个数,这就是经典的TopK问题,这种问题在实际的业务非常的常见,比如微博的热搜排名,抖音的每日热榜排名等等都是属于这种Top问题。...
  • 刷题 | top k问题

    千次阅读 2022-03-09 20:51:16
    包含排序 sort--排全部 冒泡等--排k个 n*k 快排--nlogn的复杂度,但是是在平均的情况下,最糟糕的情况依然是n方 不含排序 随机选择--用快排的思想,但只递归一边 是On(哼哼,某厂面试官还...) 堆--以最小k个为例,...
  • TopK问题的Java实现

    千次阅读 2018-04-11 10:57:11
    面试中会经常遇到手撕代码的情况,而求TopK的是经常遇到的题目。下面我就用Java来实现。主要通过两种方法实现,快排思想... * 使用快排实现的TopK问题 Title: Description: Company: * * @author 郑伟 * @date 201
  •   快排求TopK思路:假设n个数存储在数组S中,从S中找出一个元素X,它把数组分为比它大的和比它小的两部分,假设比它大的一部分数组是Smax,比它小的部分是Smin。 这时有两种可能:   1. Smax中元素不足K个,...
  • topK问题,就是找出序列中前k大(或小)的数,topK问题和第K大(或小)的解题思路其实大致一致的。 TopK问题是一个非常经典的问题,在笔试和面试中出现的频率都非常非常高(从不说假话)。下面,从小小白的出发点,认为to
  • TOPK问题,在一堆无序数组中找到最大或者最小的K个数。一般使用快速排序,然后查找K个数字,时间复杂度最好在nlog,最坏情况O(n2)。而BFPRT算法,又叫做中位数的中位数算法,由五个发明人的名字缩写构成,其最坏的...
  • top k 问题的几种解决方法

    千次阅读 2018-02-22 17:30:53
    top k问题是指给定一组数量为n的数,从中找出前k大的数或第k大的数(k &lt;= n)。由于只要能找出前k大的数,即可以得到第k大的数。所以下面先介绍解决前k大数问题的几种思路: 1.部分排序 由于我们只需要找到...
  • 海量数据中找出前k大数(topk问题

    千次阅读 2019-02-25 20:58:16
    前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。  先拿10000个数建堆,然后一次...
  • TopK问题三种方法总结

    千次阅读 2020-02-07 17:34:35
    TopK问题三种方法总结 文章目录TopK问题三种方法总结what's topK?堆解题步骤具体实现summaryquickSelect解题步骤具体实现summary二分法解题步骤具体实现summaryleetcode-719-找出第 k 小的距离对leetcode-378-有序...
  • 这其实就是一个Top k问题,如何从亿万级的数据中得到前K个最大或者最小的数字。 一个复杂度比较低的算法就是利用最小堆算法,它的思想就是:先建立一个容量为K的最小堆,然后遍历这几千亿个数,如果对于遍历到的数...
  • 最小堆解决Top K问题

    千次阅读 2016-11-18 17:11:51
    问题描述:有一组数据n个,要求取出这组数据中最大的K个值。 对于这个问题,解法有很多中。比如排序及部分排序,不过效率最高的要数最小堆,它的时间复杂度为O(nlogk)。 解题思路: 取出数组的前n个元素,创建长度...
  • 题目:分析求解topk(big)问题时 堆排序 和 快速排序 的使用场景 快速排序求解 &nbsp; &nbsp; &nbsp; &nbsp;这种算法利用了快速排序的主要思想:每次调用快速排序的partition函数后将会得出一个数n...
  • topK问题

    千次阅读 2018-10-24 17:47:54
    topK问题:给定一批数,如n个, 然后从中找出k个最大(小)的数。 具体一个场景,比如给出1000w个数,找出最大的100个。 思路有以下几个: 先排序,取出最大的几个,伪代码如下: sort(arr, 1, n) return arr[1, k...
  • # i太小了,Topk在右边 return quickSort ( points , i + 1 , hi , k ) elif hi < k + i - 1 : # Topk在左边 return quickSort ( points , lo , i - 1 , k - ( hi - i + 1 ) ) else :...
  • c++ topk问题

    千次阅读 2020-12-05 20:11:49
    minHeap.empty()) { //输出最大的K个数 cout << minHeap.top() ; minHeap.pop(); } return 0; } /*第二种情况——Quick Select C++代码实现*/ /*Quick Select*/ #include #include using namespace std; int ...
  • 大根堆小根堆&TopK问题

    千次阅读 2019-07-28 09:32:46
    大根堆用于升序排序(所以求最小的前k个数用大根堆),小根堆用于降序排序(所以求最大的前k个数(常见的topk问题,基本都是求最大的前k个数)用小根堆)。 堆排序的时间复杂度是O(NlogN),空间复杂度是O(1),所以...
  • 给定两个有序数组arr1和arr2,再给定一个整数k,返回来自arr1和arr2的两个数相加和最大的前k个,两个数必须分别来自两个数组 要求: 1. 按照降序输出 2. 时间复杂度为O(klogk) 题目分析 这道题的正确解法为...
  • Top k问题(线性时间选择算法)

    千次阅读 2016-04-25 18:38:24
    Top k问题(线性时间选择算法)
  • =k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。 注意:题中只需得到最大的K个数,而不需要对后面N-K个数排序 可能存在的条件限制: 要求 时间 和 空间消耗最小、海量数据、待排序的数据可能是...
  • LeetCode Top K 问题

    千次阅读 2018-11-30 11:52:48
    给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 说明: 你可以假设给定的 k 总是合理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 410,446
精华内容 164,178
关键字:

topk问题