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;
}
运行结果
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));
}
运行结果
上一篇: Java Web项目中编写定时任务的实现
下一篇: pandas 数据统计