求Top K问题

1.大小根堆解决Top k问题

传统思想：是将容器中的数据进行排序，排序的时间复杂度最差像冒泡是O(n^2),最好像快排是O(nlogn)。

如何在线性时间内O(n)找到Top K的元素呢?

相当于将原始序列遍历一遍就可以找到相应的元素，其实也没有必要将所有的元素进行排序，其他的元素有不有序并不关心。因此就可以使用大小根堆过滤Top K问题。

实际应用：互联网公司的智能推荐，像用户使用频率最高的一些应用，一些热点新闻，搜索频率最高的一些关键字等等

原始序列：64 45 52 80 66 68 0 2 18 75
如何求出序列中最小/大的前3个元素？

最小Top K

思想：

求最小就使用大根堆：将大根堆堆顶的大值不断淘汰，放入小值

步骤：

• 1.先遍历序列的前K个元素，将其构建成一个大根堆

• 2.不断淘汰堆顶的大值。插入小于堆顶的元素，出堆顶元素，平衡大顶堆
  

// 求vec中值最小的前5个元素
int main()
{
    vector<int> vec;
    srand(time(NULL));
    for (int i = 0; i < 1000; i++)
    {
        vec.push_back(rand() % 10000);
    }
    // 求vec中值最小的前5个元素
    priority_queue<int> maxheap;
    int k = 5;

    // 由前k个元素构建一个大根堆
    for (int i = 0; i < 5; i++)
    {
        maxheap.push(vec[i]);
    }

    // 遍历剩余的元素直到最后
    for (int i = 5; i < vec.size(); i++)
    {
        if (maxheap.top() > vec[i])
        {
            maxheap.pop();
            maxheap.push(vec[i]);
        }
    }

    // 输出结果
    while (!maxheap.empty())
    {
        cout << maxheap.top() << " ";
        maxheap.pop();
    }
    cout << endl;
}

最大Top K

求最大就使用小根堆：将小根堆堆顶的小值不断淘汰，放入大值

步骤：

• 1.先遍历序列的前K个元素，将其构建成一个小根堆
  
• 2.不断淘汰堆顶的小值。插入大于堆顶的元素，出堆顶元素，平衡小顶堆
  

int main()
{
    vector<int> vec;
    srand(time(NULL));
    for (int i = 0; i < 1000; i++)
    {
        vec.push_back(rand() % 10000);
    }
    // 求vec中值最大的前5个元素
    priority_queue<int, vector<int>, greater<int>> minheap;
    int k = 5;

    // 由前k个元素构建一个小根堆
    for (int i = 0; i < 5; i++)
    {
        minheap.push(vec[i]);
    }

    // 遍历剩余的元素直到最后
    for (int i = 5; i < vec.size(); i++)
    {
        if (minheap.top() < vec[i])
        {
            minheap.pop();
            minheap.push(vec[i]);
        }
    }

    // 输出结果
    while (!minheap.empty())
    {
        cout << minheap.top() << " ";
        minheap.pop();
    }
    cout << endl;

}

找第K小或者第K大访问堆顶就行了

2.快排分割解决Top K

快排详解

利用快排分割函数每次返回的基准数的位置，找出前top k大的或者前top k小的数据

//

#include <iostream>
using namespace std;

// 快排分割函数
int Partation(int arr[], int begin, int end)
{
    int val = arr[begin];
    int i = begin;
    int j = end;

    while (i < j)
    {
        while(i < j&& arr[j] < val)
            j--;

        if (i < j)
        {
            arr[i] = arr[j];
            i++;
        }

        while (i < j && arr[i] > val)
            i++;

        if (i < j)
        {
            arr[j] = arr[i];
            j--;
        }
    }

    arr[i] = val;
    return i;
}

// 求top k的函数
void SelectTopK(int arr[], int begin, int end, int k)
{
    int pos = Partation(arr, begin, end);
    if (pos == k - 1)
    {
        return;
    }
    else if (pos > k - 1)
    {
        SelectTopK(arr, begin, pos - 1, k);
    }
    else
    {
        SelectTopK(arr, pos + 1, end, k);
    }
}

int main()
{
    int arr[] = { 64, 45, 52, 80, 66, 68, 0, 2, 18, 75 };
    int size = sizeof arr / sizeof arr[0];

    // 求值最小的前3个元素
    int k = 3;
    SelectTopK(arr, 0, size - 1, k);

    for (int i = 0; i < k; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

大文件求Top K

3.查重+Top K(重复次数最大的Top K)

统计重复次数最小的前K个数字

思路：
由于是统计重复次数最小，并且最终输出的是元素。

• 1.首先使用哈希表统计每个元素的重复次数，并记录
• 2.将哈希表的前K个key-value作为pair插入堆，进行堆排（要注意自定义类型要改变比较器的比较规则）
• 3.遍历哈希表，找出前K个元素

// 统计重复次数最小的前3个数字
int main()
{
    vector<int> vec;
    srand(time(NULL));
    for (int i = 0; i < 10000; i++)
    {
        vec.push_back(rand() % 1000);
    }

    // 统计重复次数最小的前3个数字
    int k = 3;
    unordered_map<int, int> map;
    for (auto key : vec)
    {
        map[key]++;
    }

    // 放入大根堆的时候，需要放key-value键值对
    using Type = pair<int, int>;
    using Comp = function<bool(Type&, Type&)>;
    priority_queue<Type, vector<Type>, Comp> maxheap(
        [](Type& a, Type& b)->bool {
            return a.second < b.second;//大根堆默认比较器是less，所以自定义的比较方法也应该是小于
        });

    auto it = map.begin();
    for (int i = 0; i < k; i++, ++it)
    {
        maxheap.push(*it);
    }

    for (; it != map.end(); ++it)
    {
        if (maxheap.top().second > it->second)
        {
            maxheap.pop();
            maxheap.push(*it);
        }
    }

    while (!maxheap.empty())
    {
        cout << "key:" << maxheap.top().first
            << " cnt:" << maxheap.top().second << endl;
        maxheap.pop();
    }
}

统计重复次数最大的前K个数字

int main()
{
    vector<int> vec;
    srand(time(NULL));
    for (int i = 0; i < 10000; i++)
    {
        vec.push_back(rand() % 1000);
    }

    // 统计重复次数最大的前3个数字
    int k = 3;
    unordered_map<int, int> map;
    for (auto key : vec)
    {
        map[key]++;
    }

    // 放入大根堆的时候，需要放key-value键值对
    using Type = pair<int, int>;
    using Comp = function<bool(Type&, Type&)>;
    priority_queue<Type, vector<Type>, Comp> minheap(
        [](Type& a, Type& b)->bool {
            return a.second > b.second;
        });

    auto it = map.begin();
    for (int i = 0; i < k; i++, ++it)
    {
        minheap.push(*it);
    }

    for (; it != map.end(); ++it)
    {
        if (minheap.top().second < it->second)
        {
            minheap.pop();
            minheap.push(*it);
        }
    }

    while (!minheap.empty())
    {
        cout << "key:" << minheap.top().first
            << " cnt:" << minheap.top().second << endl;
        minheap.pop();
    }
}

大文件

// 大文件划分小文件（哈希映射）+ 哈希统计 + 小根堆(快排也可以达到同样的时间复杂度)
int main()
{
	//通过下面的代码，先生成放整数的二进制文件：
	FILE* pf1 = nullptr;
	errno_t res =fopen_s(&pf1,"data.dat", "wb");
	for (int i = 0; i < 20000; ++i)
	{
		int data = rand();
		if (data < 0)
			cout << data << endl;
		fwrite(&data, 4, 1, pf1);//将data写入pf1,数据类型4字节，写1个
	}
	fclose(pf1);



	// 打开存储数据的原始文件
	FILE* pf = nullptr;
		errno_t res2=fopen_s(&pf,"data.dat", "rb");
	if (pf == nullptr)
		return 0;

	// 这里由于原始数据量缩小，所以这里文件划分的个数也变小了，11个小文件
	const int FILE_NO = 11;
	FILE* pfile[FILE_NO] = { nullptr };
	for (int i = 0; i < FILE_NO; ++i)
	{
		char filename[20];
		sprintf_s(filename, "data%d.dat", i + 1);
		 
			errno_t res1 = fopen_s(&pfile[i],filename, "wb+");
	}

	// 哈希映射，把大文件中的数据，映射到各个小文件当中
	int data;
	while (fread(&data, 4, 1, pf) > 0)
	{
		int findex = data % FILE_NO;
		fwrite(&data, 4, 1, pfile[findex]);
	}

	// 定义一个链式哈希表
	unordered_map<int, int> numMap;
	// 先定义一个小根堆
	using P = pair<int, int>;
	using FUNC = function<bool(P&, P&)>;
	using MinHeap = priority_queue<P, vector<P>, FUNC>;
	MinHeap minheap([](auto& a, auto& b)->bool {
		return a.second > b.second; // 自定义小根堆元素大小比较方式
		});

	// 分段求解小文件的top 10大的数字，并求出最终结果
	for (int i = 0; i < FILE_NO; ++i)
	{
		// 恢复小文件的文件指针到起始位置
		fseek(pfile[i], 0, SEEK_SET);

		while (fread(&data, 4, 1, pfile[i]) > 0)
		{
			numMap[data]++;
		}

		int k = 0;
		auto it = numMap.begin();

		// 如果堆是空的，先往堆方10个数据
		if (minheap.empty())
		{
			// 先从map表中读10个数据到小根堆中，建立top 10的小根堆，最小的元素在堆顶
			for (; it != numMap.end() && k < 10; ++it, ++k)
			{
				minheap.push(*it);
			}
		}

		// 把K+1到末尾的元素进行遍历，和堆顶元素比较
		for (; it != numMap.end(); ++it)
		{
			// 如果map表中当前元素重复次数大于，堆顶元素的重复次数，则替换
			if (it->second > minheap.top().second)
			{
				minheap.pop();
				minheap.push(*it);
			}
		}

		// 清空哈希表，进行下一个小文件的数据统计
		numMap.clear();
	}

	// 堆中剩下的就是重复次数最大的前k个
	while (!minheap.empty())
	{
		auto& pair = minheap.top();
		cout << pair.first << " : " << pair.second << endl;
		minheap.pop();
	}

	return 0;
}