c++ - 在 1.5 秒内找到超过 2000 万个 3 到 4 个不同整数的中位数
问题描述
我正在尝试排序并找到仅包含 3 到 4 个不同整数的整数字符串的中位数。
我正在处理的数字数量约为 20 到 2500 万,我应该对向量进行排序并在每次将新整数添加到向量中时找到中值并将中值添加到单独的“总计”变量中每次生成中位数时,它会汇总所有中位数。
1 Median: 1 Total: 1
1 , 2 Median: (1+2)/2 = 1 Total: 1 + 1 = 2
1 , 2 , 3 Median: 2 Total: 2 + 2 = 4
1 , 1 , 2 , 3 Median: (1+2)/2 = 1 Total: 4 + 1 = 5
1 , 1 , 1 , 2 , 3 Median: 1 Total: 5 + 1 = 6
我正在尝试找到一种方法来进一步优化我的代码,因为它不够高效。(必须在 2 秒左右的时间内处理)有谁知道如何进一步加快我的代码逻辑?
我目前在 C++ 中使用 2 个堆或优先级队列。一个用作最大堆,另一个用作最小堆。
You can use 2 heaps, that we will call Left and Right.
Left is a Max-Heap.
Right is a Min-Heap.
Insertion is done like this:
If the new element x is smaller than the root of Left then we insert x to
Left.
Else we insert x to Right.
If after insertion Left has count of elements that is greater than 1 from
the count of elements of Right, then we call Extract-Max on Left and insert
it to Right.
Else if after insertion Right has count of elements that is greater than the
count of elements of Left, then we call Extract-Min on Right and insert it
to Left.
The median is always the root of Left.
So insertion is done in O(lg n) time and getting the median is done in O(1)
time.
但这还不够快...
解决方案
如果您在字符串中只有三到四个不同的整数,您可以通过遍历字符串一次来跟踪每个整数出现的次数。从此表示中添加(和删除元素)也可以在恒定时间内完成。
class MedianFinder
{
public:
MedianFinder(const std::vector<int>& inputString)
{
for (int element : inputString)
_counts[element]++; // Inserts 0 into map if element is not in there.
}
void addStringEntry(int entry)
{
_counts[entry]++;
}
int getMedian() const
{
size_t numberOfElements = 0;
for (auto kvp : _counts)
numberOfElements += kvp.second;
size_t cumulativeCount = 0;
int lastValueBeforeMedian;
for (auto kvp : _counts)
{
cumulativeCount += kvp.second;
if (cumulativeCount >= numberOfElements/2)
lastValueBeforeMedian = kvp.first;
}
// TODO! Handle the case of the median being in between two buckets.
//return ...
}
private:
std::map<int, size_t> _counts;
};
这里没有显示对中位数求和的琐碎任务。
推荐阅读
- vue.js - 在 chrome 开发工具上以调试模式启动 jest 测试时,不会加载 .env 文件中的环境变量
- python - Drawing circles based on user input
- android - 在android中完全停止并重新启动Vuforia相机,停止工作,但重新启动没有
- r - 用未知替换NA
- java - 在实现带有参数 E e 的方法时如何解决有关超类型的错误?
- reactjs - 当 scrollTop 为零时,在渲染后反应滚动位置
- xpath - Complex XPath axes/where (BizTalk EDI 856 Schema)
- java - Illegal static declaration in inner class while using ActionListener
- typescript - 如何为动态添加的方法定义方法签名?
- docker - Docker is pulling image from remote registry but I want to use a local image