我想在这里讨论一个我在数据结构书中找到的算法.本书提供了算法的草图,以便在大小为N的数组中找到多数元素(出现多于N/2).算法草图如下:
首先,找到候选多数元素(这是更难的部分).这个候选人是唯一可能成为多数元素的元素.第二步确定这个候选人是否实际上是多数.这只是对数组的顺序搜索.要在数组中找到候选项A,形成第二个数组B.然后比较A1,A2.如果它们相等,则将其中一个添加到B; 否则什么也不做.然后比较A3和A4.如果它们相等,再将其中一个添加到B; 否则什么也不做.以这种方式继续,直到读取整个数组.然后递归地找到B的候选者; 这是A的候选人.
我想出如果N是偶数,算法工作正常.但如果N是奇数怎么办？我们如何处理这个案子？
ban*_*run -1
我认为当 N 也是偶数时你的算法将不起作用。我可以用一个例子来证明：
考虑 8 个元素的数组，例如 2,2,1,1,3,2,2,2。现在，根据您的陈述，您的 B 数组将是 2,1,2。如果再重复上面的步骤。不会有任何候选人。但这里的实际答案是“2”。所以这个方法肯定是错误的。
这个问题在 Geeks for Geeks 上进行了讨论。我认为这会对您有所帮助：
http://www.geeksforgeeks.org/majority-element/