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

我正在使用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
伪代码找到大多数项，并且至少需要一半。我只想找到多数项目。
我能找人帮忙吗？
谢谢！

最佳答案

我写了一个迭代版本，而不是递归版本，如果你想要类似的东西的话。

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%以上（占多数）时返回值。否则它会遍历整个数组并以最大的频率返回值。

关于python - 分而治之。查找数组中的大多数元素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57789350/