在数组中出现n / 3次以上的数字 [英] number which appears more than n/3 times in an array

问题描述

我已经阅读了此问题
找到数组中最常见的条目

，乔恩·斯凯特（jon skeet）的回答很令人震惊..：）

现在我正在尝试解决此问题，以找到在数组中出现n / 3次以上的元素..

我很确定我们不能应用相同的方法，因为可能有2个这样的元素发生的次数超过n / 3次，并且会给计数带来错误的警报。.因此，有什么方法可以调整乔恩·斯凯特的答案来解决这个问题。 / p>

或者是否有任何可以线性运行的解决方案？

解决方案

Jan Dvorak的答案可能是最好的：

• 以两个空的候选位置和两个计数器设置为0开始。


• 每个项目：
  
  
  
  如果它等于任一候选者，则在没有空位的情况下增加相应的计数
  
  • else（即一个计数为0的插槽，将其放入该插槽并将计数设置为1
  
  
  • else将两个计数器都减少1
  
  

最后，对数组进行第二遍检查以检查候选人是否确实具有所需的计数。您链接到的问题不允许这样做，但我看不到如何针对此修改版本避免这种情况。如果某个值的出现次数超过n / 3次，则它将位于一个插槽中，但您不知道它是哪个插槽。

如果对此值进行了修改该问题的版本保证存在两个值大于个元素（通常， k-1 的值超过 n / k ），那么我们就不需要第二遍了。但是，当原始问题具有 k = 2 且有1个保证多数时，就无法知道我们是否应该将其推广为保证1个这样的元素或保证 k-1 。担保越严格，问题越容易解决。

I have read this problem Find the most common entry in an array

and the answer from jon skeet is just mind blowing .. :)

Now I am trying to solve this problem find an element which occurs more than n/3 times in an array ..

I am pretty sure that we cannot apply the same method because there can be 2 such elements which will occur more than n/3 times and that gives false alarm of the count ..so is there any way we can tweak around jon skeet's answer to work for this ..?

Or is there any solution that will run in linear time ?

解决方案

Jan Dvorak's answer is probably best:

• Start with two empty candidate slots and two counters set to 0.
• for each item:
  • if it is equal to either candidate, increment the corresponding count
  • else if there is an empty slot (i.e. a slot with count 0), put it in that slot and set the count to 1
  • else reduce both counters by 1

At the end, make a second pass over the array to check whether the candidates really do have the required count. This isn't allowed by the question you link to but I don't see how to avoid it for this modified version. If there is a value that occurs more than n/3 times then it will be in a slot, but you don't know which one it is.

If this modified version of the question guaranteed that there were two values with more than n/3 elements (in general, k-1 values with more than n/k) then we wouldn't need the second pass. But when the original question has k=2 and 1 guaranteed majority there's no way to know whether we "should" generalize it as guaranteeing 1 such element or guaranteeing k-1. The stronger the guarantee, the easier the problem.

这篇关于在数组中出现n / 3次以上的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！