欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Top K 问题的几种解法

程序员文章站 2024-03-07 16:54:51
...

1. 先排序后取K个数。 时间复杂度O(nlgn).

vector<int> FindSmallestKNum(vector<int> &vec, int k)
{
	if (vec.size() < k)
		return vector<int>();

	sort(vec.begin(), vec.end());

	return vector<int>(vec.begin(), vec.begin()+k);
}

2. 插入排序。先取k个数,不断替换掉其中的最大值,时间复杂度为O(n*k)。

vector<int> FindSmallestKNum(vector<int> &vec, int k)
{
	if (vec.size() < k)
		return vector<int>();

	vector<int> out(vec.begin(), vec.begin() + k);
	for(int ii = k; ii<vec.size(); ++ii)
	{
		auto tar_it = max_element(out.begin(), out.end());
		int idx = tar_it - out.begin();
		if (vec[ii] < out[idx])
		{
			out[idx] = vec[ii];
		}
	}

	return out;
}

3. 快速选择算法。平均时间复杂度O(n).

int Partition(vector<int>& vec, int first_idx, int last_idx)
{
	if (vec.empty())
		return -1;

	if (first_idx == last_idx)
		return first_idx;

	int pivot = vec[first_idx];
	int ii = first_idx, jj = first_idx + 1;
	for (; jj <= last_idx; ++jj)
	{
		if (vec[jj] > pivot)
		{
			swap(vec[jj], vec[++ii]);
		}
	}

	swap(vec[first_idx], vec[ii]);

	return ii;
}

vector<int> QuickSelect(vector<int>& vec, int k)
{
	if (vec.empty() || vec.size()<k)
		return vector<int>();

	int first_idx = 0, last_idx = vec.size() - 1;
	vector<int> out;
	while (first_idx <= last_idx)
	{
		int mid_idx = Partition(vec, first_idx, last_idx);

		if (mid_idx == k-1)
		{
			for (int ii = 0; ii < k; ++ii)
			{
				out.push_back(vec[ii]);
			}
			break;
		}
		else if (mid_idx < k - 1)
		{
			first_idx = mid_idx + 1;
		}
		else if (mid_idx > k - 1)
		{
			last_idx = mid_idx - 1;
		}
	}

	return out;
}

运行结果

Top K 问题的几种解法

4. 计数排序。用例数据波动范围小且为整型。时间复杂度O(n)。

使用bitmap来进行排序及统计。

#define SHIFT 5
#define MASK 0x1F

void SetBit(vector<int>& vec, int kk)
{
	vec[kk >> SHIFT] |= ( (0x01)<<(kk&MASK) );   //kk&MASK 相当于 kk%32
}

void ClearBit(vector<int>&vec, int kk)
{
	vec[kk >> SHIFT] &= ~((0x01) << (kk&MASK));
}

bool GetBit(vector<int>&vec, int kk)
{
	return vec[kk >> 5] & ((0x01) << (kk&MASK));
}

运行结果

Top K 问题的几种解法