python - 分而治之。查找数组中的大多数元素

Question

我正在研究一种 python 算法来查找列表中出现频率最高的元素。

def GetFrequency(a, element):
return sum([1 for x in a if x == element])

def GetMajorityElement(a):
  n = len(a)
  if n == 1:
    return a[0]
  k = n // 2

  elemlsub = GetMajorityElement(a[:k])
  elemrsub = GetMajorityElement(a[k:])
  if elemlsub == elemrsub:
    return elemlsub

  lcount = GetFrequency(a, elemlsub)
  rcount = GetFrequency(a, elemrsub)

  if lcount > k:
    return elemlsub
  elif rcount > k:
    return elemrsub
  else:
    return None

我尝试了一些测试用例。其中一些通过了，但也有一些失败了。

例如，[1,2,1,3,4] 这应该返回 1，但我没有得到。

实现遵循这里的伪代码: http://users.eecs.northwestern.edu/~dda902/336/hw4-sol.pdf 伪代码找到多数项并且至少需要一半。我只想找到多数项目。

我能得到一些帮助吗？ 谢谢!

Answer 1

我写了一个迭代版本而不是你正在使用的递归版本，以防你想要类似的东西。

def GetFrequency(array):
    majority = int(len(array)/2)
    result_dict = {}
    while array:
        array_item = array.pop()
        if result_dict.get(array_item):
            result_dict[array_item] += 1
        else:
            result_dict[array_item] = 1
        if result_dict[array_item] > majority:
            return array_item   
    return max(result_dict, key=result_dict.get)

这将遍历数组并在一个命中超过总数的 50%(即多数)时立即返回值。否则它会遍历整个数组并返回频率最高的值。