分而治之。查找数组中的大多数元素 [英] Divide and Conquer. Find the majority of element in array

问题描述

我正在研究python算法，以查找列表中最常出现的元素。

I am working on a python algorithm to find the most frequent element in the list.

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

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

I tried some test cases. Some of them are passed, but some of them fails.

例如，[1,2,1,3,4]应该返回1，但是我得到的结果是None

For example, [1,2,1,3,4] this should return 1, buit I get None.

该实现遵循以下伪代码：
http://users.eecs.northwestern.edu/~dda902/336/hw4-sol.pdf
伪代码可找到多数项和需求至少要一半我只想找到多数物品。

The implementation follows the pseudocode here: http://users.eecs.northwestern.edu/~dda902/336/hw4-sol.pdf The pseudocode finds the majority item and needs to be at least half. I only want to find the majority item.

我可以得到一些帮助吗？
谢谢！

Can I get some help? Thanks!

推荐答案

def majority_element(a):
    return max([(a.count(elem), elem) for elem in set(a)])[1]

编辑

如果出现平局，则返回最大值。例如： a = [1,1,2,2] 返回2。可能不是您想要的，但是可以更改。

If there is a tie, the biggest value is returned. E.g: a = [1,1,2,2] returns 2. Might not be what you want but that could be changed.

编辑2

您提供的伪代码分为数组1到k 包括，k +1至n。您的代码会以1到k-1，k结束，但是不确定代码是否有很大变化？如果要遵守给出的算法，则应该执行以下操作：

The pseudocode you gave divided into arrays 1 to k included, k + 1 to n. Your code does 1 to k - 1, k to end, not sure if it changes much though ? If you want to respect the algorithm you gave, you should do:

elemlsub = GetMajorityElement(a[:k+1])  # this slice is indices 0 to k
elemrsub = GetMajorityElement(a[k+1:])  # this one is k + 1 to n.

也仍然根据您提供的伪代码 lcount 和 rcount 应该与 k + 1 而不是 k ：

Also still according to your provided pseudocode, lcount and rcount should be compared to k + 1, not k:

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

编辑3

有些人认为提供伪代码并不能解决最常见的问题，而解决的问题是发生次数的50％。因此，您的示例输出确实是正确的。

Some people in the comments highligted that provided pseudocode solves not for the most frequent, but for the item which is present more that 50% of occurences. So indeed your output for your example is correct. There is a good chance that your code already works as is.

编辑4

如果要在出现平局时返回 None ，我建议这样做：

If you want to return None when there is a tie, I suggest this:

def majority_element(a):
    n = len(a)
    if n == 1:
        return a[0]

    if n == 0:
        return None

    sorted_counts = sorted([(a.count(elem), elem) for elem in set(a)], key=lambda x: x[0])

    if len(sorted_counts) > 1 and sorted_counts[-1][0] == sorted_counts[-2][0]:
        return None

    return sorted_counts[-1][1]

这篇关于分而治之。查找数组中的大多数元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！