Ani*_*tti 13 language-agnostic algorithm complexity-theory
有人能想到用于确定元素列表中的多数元素的线性时间算法吗？算法应该使用O(1)空间.
如果n是列表的大小,则多数元素是至少出现一次的元素ceil(n / 2).
[Input] 1, 2, 1, 1, 3, 2
[Output] 1
[编者注]这个问题存在技术错误.我宁愿离开它,以免破坏接受的答案的措辞,纠正错误并讨论原因.请检查接受的答案.
Mat*_*ery 14
我猜想Boyer-Moore算法(由nunes链接并在其他答案中由cldy描述)是问题的预期答案; 但问题中"多数元素"的定义太弱,无法保证算法能够正常工作.
如果n是列表的大小.多数元素是至少出现ceil(n/2)次的元素.
如果存在这样的元素,Boyer-Moore算法会找到具有严格多数的元素.(如果您事先不知道您确实有这样的元素,则必须在列表中进行第二次检查以检查结果.)
对于绝对多数,你需要"......严格超过地板(n/2)次",而不是"......至少ceil(n/2)次".
在您的示例中,"1"出现3次,其他值出现3次:
输入示例:1,2,1,1,3,2
输出:1
但是你需要4个具有相同值的元素才能获得严格的多数.
它确实适用于这种特殊情况:
Input: 1, 2, 1, 1, 3, 2 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 1: count != 0, element == candidate (1), so increment count to 2 Read 3: count != 0, element != candidate (1), so decrement count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Result is current candidate: 1
但看看如果最后的"1"和最后的"2"被交换会发生什么:
Input: 1, 2, 1, 2, 3, 1 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Read 1: count == 0, so set candidate to 1, and set count to 1 Read 2: count != 0, element != candidate (1), so decrement count to 0 Read 3: count == 0, so set candidate to 3, and set count to 1 Read 1: count != 0, element != candidate (3), so decrement count to 0 Result is current candidate: 3
小智 9
Boyer-moore算法:http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
您扫描列表(或流)并维护一个计数器.最初counter = 0,majority_element = null.在扫描时,如果计数器为0,则假定当前元素为多数元素并增加计数器.如果counter != 0,则根据当前元素是否是当前多数元素来递增或递减计数器.
如果没有这个算法,这个算法不会给你多数.如果你想要正确的程度,你将不得不再做一次验证它实际上是大多数(即> = 50%).
我认为这是可能的,使用Boyer-Moore,虽然不是直接的.
正如马修所说,Boyer-Moore只保证找到多数元素,对多数的定义略有不同,称为严格多数.你的定义稍微弱一点,但不是很多.
1.和2.步骤是直截了当的.3.因为通过删除失败的候选者的实例,我们现在正在寻找严格的多数元素.4.是可选的,只有在可能不存在多数元素时才使用.