421-分治算法-快速划分函数求topk

谁践踏了优雅 2022-09-05 04:04 176阅读 0赞

**在一组数据中求前10大的元素，或者求前10小的元素，或者第10小的元素，诸如此类问题。**

## 求大数的topk问题 ##

**解法1：用大根堆或者小根堆 优先级队列  
解法2：用快排的划分函数**  
![在这里插入图片描述][3a05c548952a4479a5b341ca6494e263.png]

**我们先回忆一下大根堆，小根堆：**  
**比如说**：  
这里有10万个整数，值最大的第10个元素，或者求值最大的前10个元素。  
我们拿最开始的前K（10）个元素，组成一个小根堆（找值大的），堆顶的元素值最小。  
**第11-10万个元素(cur)和堆顶元素top进行比较。**  
如果说top>cur。说明小根堆的元素是目前最大的。  
如果说top<cur。说明小根堆的元素不是最大的。  
此时就要把top出堆，或者出优先级队列，然后把cur元素入堆。继续遍历下去直到遍历完。堆顶元素就是第10大的。整个堆的元素就是前10大的。  
**这个算法的时间复杂度是O(n)：因为它把所有元素都遍历1遍，每一个元素和堆顶元素比较是一个常量时间，但是都有可能影响堆顶，就是从堆顶添加或者删除元素，堆的调整是logk，因为堆里永远维护的是10个元素，也是常量，所以时间复杂度是O(n）**

**我们来用快排的划分函数看看：**  
这个基准数怎么看，它的左边都比基准数小，它的右边都比基准数大。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**所以这个基准数41就是第5小，第7大**  
**所以我们就返回基准数的位置l，如果这个l刚好就等于要求的k值，就算已经完成了！**

**如果你要找第k大的元素**，我们通过划分函数，得到一个l，找第k大的实际上就是找length-k=4，如果l就是4，就是找到了。如果l==length-k,证明已经找到了。  
如果l>length-k。说明是落在l的左边，就是在l左边继续进行快排划分。继续和length-k比较。反之则反。

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    //快排划分函数，调整基准数
    static int partation(vector<int>& vec, int i, int j)
    {
        
    	int val = vec[i];//作为基准数
    	int l = i;
    	int r = j;
    	while (l < r)
    	{
        
    		while (l < r && vec[r] >= val)
    		{
        // 右 - 左  找第一个比val小的
    			r--;
    		}
    		if (l < r)
    		{
        
    			vec[l++] = vec[r];
    		}
    		while (l < r && vec[l] < val)
    		{
        // 左 - 右  找第一个比val大的
    			l++;
    		}
    		if (l < r)
    		{
        
    			vec[r--] = vec[l];
    		}
    	}
    	vec[l] = val; //放置基准数
    	return l;//返回基准数的下标
    }
    
    //找第k大的， vec.size()-k 小的 下标
    int max_select_topk(vector<int>& vec, int i, int j, int k)
    {
        
    	int pos = partation(vec, i, j);//pos表示基准数的位置
    	if (pos == vec.size() - k)
    	{
         //基准数的位置和top k的k值相等了
    		return pos;
    	}
    	else if (pos < vec.size() - k)
    	{
         //topk应该在基准数的右边
    		return max_select_topk(vec, pos + 1, j, k);
    	}
    	else
    	{
        
    		//topk应该落在基准数的左边
    		return max_select_topk(vec, i, pos - 1, k);
    	}
    }
    
    //找第k小的，  k-1小的 下标   3
    int min_select_topk(vector<int>& vec, int i, int j, int k)
    {
        
    	int pos = partation(vec, i, j); //pos表示基准数的位置
    	if (pos == k - 1)
    	{
         //基准数的位置和top k的k值相等了
    		return pos;
    	}
    	else if (pos < k - 1)
    	{
         //topk应该在基准数的右边
    		return min_select_topk(vec, pos + 1, j, k);
    	}
    	else
    	{
         //topk应该落在基准数的左边
    		return min_select_topk(vec, i, pos - 1, k);
    	}
    }
    
    int main()
    {
        
    	vector<int> vec;
    	for (int i = 0; i < 20; ++i) {
        
    		vec.push_back(rand() % 100);
    	}
    
    	//求第top 4大的元素
    	int pos = max_select_topk(vec, 0, vec.size() - 1, 4);
    	cout << "第topk大的:" << vec[pos] << endl;
    	cout << "前topk大的:";
    	for (int i = pos; i < vec.size(); ++i)
    	{
        
    		cout << vec[i] << " ";
    	}
    	cout << endl;
    
    	//找top 4小的
    	pos = min_select_topk(vec, 0, vec.size() - 1, 4);
    	cout << "第topk小的:" << vec[pos] << endl;
    	cout << "前topk小的:";
    	for (int i = 0; i <= pos; ++i)
    	{
        
    		cout << vec[i] << " ";
    	}
    	cout << endl;
    
    	sort(vec.begin(), vec.end());
    	for (int v : vec)
    	{
        
    		cout << v << " ";
    	}
    
    	cout << endl;
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]

[3a05c548952a4479a5b341ca6494e263.png]: /images/20220829/c4fc0633148a400e9900662dd3aaf8f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/a4749f09645343bfb875f2af941df12e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/759f3c3ac81a49e1b5e08b83ae2f58c6.png