，所以我解决的问题是在整个整数中找到大多数元素，大小为0＆lt;N＆lt;10^5，每个元素0＆lt;A＆lt;10^9。因此，我只需要找出严格显示哪些元素超过N/2次。
我有两种我认为都是正确的解决方案，但它们的行为并不像我对它们的复杂性的理解一样。有人可以向我解释我做错了/误解了什么？
int getMajElement(vector<int> a)
{
std::unordered_map<int, int> countMap;
std::unordered_map<int, int>::iterator it;
for (int i : a)
{
it = countMap.find(i);
if (it == countMap.end())
{
countMap.insert(std::pair<int, int>(i, 1));
}
else
{
it->second++;
}
}
int mostOfNum = 0;
int mostOfNumCount = 0;
for (std::pair<int, int> pair : countMap)
{
if (pair.second > mostOfNumCount)
{
mostOfNumCount = pair.second;
mostOfNum = pair.first;
}
}
if (mostOfNumCount > floor(a.size() / 2))
{
return mostOfNum;
}
else
{
return -1;
}
}
从我的理解中，第一个" for（int i：a）"应在o（n）时间内运行，同时查找/递增该值应在o（1）时间内进行hashmap。第二个" for（std ::对对：countmap）"循环也应在o（n）时间内运行，因为我最多遍地迭代。这将是O（n）时间。
此功能需要2.4秒才能运行n = 10^5，每个函数a = rand（）％10^9。我确保只花费时间功能，而不是设置初始值。
然后，在相同条件下，下一个需要0.70秒，但我希望第一个会更快。
第二个函数使用递归分隔和纠纷方法来解决问题，应花费O（n log（n））时间。它基本上将列表分为n个单个部分，然后检查左半部分的大多数元素是否与右半部分的大多数元素相同。如果不是，它将扫描列表以查看该部分的总体多数（值> floor（（右）/2））并将其传递回去，else -1。
有人可以向我解释是什么原因导致时间差，这只是我犯的实现错误吗？
int get_majority_element(vector<int> &a, int left, int right) {
if (left == right) return -1;
if (left + 1 == right) return a[left];
int mid = left + floor((right - left) / 2);
int leftMajority = get_majority_element(a, left, mid);
int rightMajority = get_majority_element(a, mid, right);
if(leftMajority == rightMajority)
{
return leftMajority;
}
else if (rightMajority == -1)
{
return leftMajority;
}
else if (leftMajority == -1)
{
return rightMajority;
}
else
{
int leftCount = 0, rightCount = 0;
for (int i = left; i < right; i++)
{
if (a[i] == leftMajority)
{
leftCount++;
}
else if (a[i] == rightMajority)
{
rightCount++;
}
}
if (leftCount > floor((right - left) / 2))
{
return leftMajority;
}
else if (rightCount > floor((right - left) / 2))
{
return rightMajority;
}
else
{
return -1;
}
}
return -1;
}
这太长了评论。
复杂性理论是关于随着数据的大小的增长，单个算法会发生什么。这是n->无穷大的限制。
在比较相同数据大小的两种不同算法方面，它有用得多。为什么？因为开销可以主导计算。例如，气泡排序为o（n^2）。但是（非常）小的数据集，它可以超过"更快"算法的合理实现。
正确的比较将是10^5个元素，然后是10^6，然后是10^7的每个算法的速度。也就是说，给定算法的速度如何增长。
在第一个解决方案中，尝试使用（n个显式）数量的存储桶数量初始化countMap 设置为至少3/4的预期数量的大小元素（鉴于您期望大多数人出现的事实）。
在填写该地图时，您可能会重新进行大量重新设计。unordered_map ::插入警告O(N)的最糟糕的时间复杂性：虽然在所有情况下都不会发生这种情况，但仅发生几次（带有相当大的地图）即可拧紧执行时间。链接说：
仅当新的元素数大于max_load_factor（）*bucket_count（）。
但是，等等，还有更多！！！
当max_load_factor()*bucket_count()大于元素计数时会发生什么？好吧，很可能发生冲突。鉴于任何碰撞都将进入一个以...等待的水桶...在o（1）的时间内进行哈希图。"
如果您有时间，请观看CPPCON14的这一部分以获取更多恐怖故事（无论如何都是周末）。
注意：我并不是说这样做会比第二种方法更快地制作第一个方法；可能是或可能不是这样。我所说的是应用该建议很可能会提高第一种方法的速度。
（我很高兴地说："我尝试过；这就是在相同的数据上，与和没有明确数量的存储桶"）