![]() |
1
61
为每个位保留一个整数,并为数组中的每个整数适当增加此集合。 最后,一些位的计数将超过数组长度的一半——这些位决定N。当然,计数将高于N出现的次数,但这并不重要。重要的是,任何不属于N的位 不能 出现超过一半的次数(因为N有超过一半的条目)和属于N的任何位 必须 发生的次数超过一半(因为它将在每次发生N以及任何额外的次数时发生)。 (目前没有代码-即将失去网络访问权限。不过,希望上面的内容足够清楚。) |
![]() |
3
8
只有两个变量可以做到这一点。
努力寻找最常见的数字,只有一个数字,即超过50%的群体。如果需要,不要急于添加检查
另外,我还没有测试过这段代码——使用它的风险自负。 |
![]() |
4
4
乔恩算法的伪代码(记事本C++:-)
|
![]() |
5
2
请注意,如果
下面是一个Python实现,时间复杂度为O(n):
|
![]() |
6
2
很明显,您可以通过哈希或排序来处理它,但对于潜在的无限流,您显然会耗尽内存。所以你得做点聪明的事。 多数元素是出现在数组大小一半以上的元素 因此,如果你计算某个元素的数量,减去所有其他元素的数量,得到数字0,那么你的原始元素就不能是多数元素。这是正确算法的基础: Python代码:
很明显,该算法是正确的
|
![]() |
7
0
我记得这个算法,它可能遵循也可能不遵循2K规则。它可能需要使用堆栈等重写,以避免由于函数调用而打破内存限制,但这可能是不必要的,因为它只有对数数量的此类调用。不管怎么说,我对大学里的事情有模糊的回忆,或者对这个问题有一个递归的解决方案,涉及到分而治之,秘密是当你把这些组分成两半时,其中至少有一半的值仍然超过其最大值的一半。分而治之的基本规则是你返回两个候选的最高值,其中一个是最高值,另一个是其他值(可能是第二位,也可能不是第二位)。我忘记了算法本身。 |
![]() |
8
0
buti-oxa/Jason Hernandez答案的正确性证明,假设Jason的答案与buti-oxa的答案相同,并且两者都按照所述算法的工作方式工作:
|
![]() |
John V · 是否存在单元测试无法发现的逻辑/流错误类型? 7 年前 |
![]() |
Beefster · 为什么ANSI颜色转义以“m”而不是“]”结尾? 7 年前 |
![]() |
Guillermo Gutiérrez · STR转换是如何工作的? 7 年前 |
![]() |
RudziankoÅ · 合并排序数组算法 7 年前 |
|
user8852560 · 构造函数中的验证和构造函数冲突 7 年前 |
![]() |
jav974 · 订购产品时寻找最佳价格组合的算法 7 年前 |
![]() |
hippietrail · 确定浮点数中前导零的数量 7 年前 |