在列表中找到最大元素

所以，这是我在分配中被赋予了一个问题：在列表中找到最大元素

写一个函数，大多数（一），即在发生至少len个返回一个值（）// 2 + 1次。如果a中不存在这样的元素，则该函数返回None。

作业中的想法是想出最快的方式。

我的想法是保存一个字典，其中包含每个元素的计数，然后遍历字典以查看是否有任何元素具有len（a）// 2 +1的计数。

但是，这似乎并没有很好的工作。有人能给我一个更好的解决方案并向我解释吗？出于某种原因，这让我疯狂。

这是我不好的结构化代码：

numTimes = dict() 

target = (len(a)//2)+1 
for i in range(0, len(a)): 
    numTimes[str(a[i])] += 1 

for k, v in numTimes.iteritems(): 
    if v==str(target): 
     return v 

return None

是什么驱使我疯狂的方式，渐渐的关键错误，当我尝试添加一个新的字典元素，虽然这有什么好做的问题。

来源

2013-11-22 user2417731

有趣的问题！你能提供一个你的字典的例子吗？在不知道数据结构如何的情况下，很难回答处理数据结构的问题。 – rickcnagy

添加了代码。 – user2417731

为什么要测试数字是否与作为字符串的目标相同？ –

我发现的最有效的方法是这样的：

numTimes = dict() 
target = (len(a)//2)+1 

for ele in a: 
    if ele not in numTimes: 
     numTimes[ele] = 1 
    else: 
     numTimes[ele] +=1 

    if numTimes[ele] == target: 
     return ele

当我们正在增加，我们可以检查的次数等于我们的目标中点。

来源

2013-11-24 08:04:37 user2417731

首先，考虑len(list)//2+1意味着有问题的元素需要是列表的大部分。只能有一个值或没有值满足这个。

您使用字典的感觉是正确的。您可以将每个元素的值映射到每个元素的计数。如果任何元素的数量大于len(list)//2+1那就是你的答案。

这里是统计列表中元素的最简单的方法（至少在没有使用库）：

def majority(li): 
    ''' test list li if any single element occurs in li more than len(li)//2+1 times ''' 
    count=dict() 
    tgt=len(li)//2+1 
    # count each element in li: 
    for key in li: 
     if key in count: 
      count[key]+=1 
     else: 
      count[key]=1  

    print count 
    for k, v in count.items(): 
     if v>=tgt: 
      return k  

    return None

注意两件事情。既然你最终会设置li为0的每一个值，你可以简化部分使用与一组fromkeys()方法来设置一次全部：

count={}.fromkeys(set(li),0)

您也可以看看，如果你得到了多数因为你是加起来的元素：

def majority2(li): 
    ''' test list li if any single element occurs in li more than len(li)//2+1 times ''' 
    count={}.fromkeys(set(li),0) 
    tgt=len(li)//2+1 
    # count each element in li: 
    for key in li: 
     count[key]+=1 
     if count[key]>=tgt: 
      return key 
    return None

测试：

>>> a=['1']*10+['2']*11 
>>> majority(a) 
{'1': 10, '2': 11} 
'2' 
>>> majority2(a) 
'2' 
>>> a=['1']*10+['2']*10 
>>> majority2(a) 
None

来源

2013-11-22 03:46:55 dawg

（Downvote是针对风格，非特定变量名称，缺乏意见。） – stalepretzel

@stalepretzel：你说得对。我大幅改变了它。感谢您的建设性反馈。 – dawg

啊，很酷。不再值得投降，downvote被删除！ :) 虽然我们谈论风格的话题，但我应该插入PEP 8（http://www.python.org/dev/peps/pep-0008/）。 – stalepretzel

我会用Counter from collections库。这是字典的一个子类。

from collections import Counter 

def majority(iterable): 
    c = Counter(iterable) 
    value, count = c.most_common(1)[0] 
    target = (len(iterable)//2) + 1 
    if (count >= target): 
     return value 
    else: 
     return None

来源

2013-11-22 04:03:50 Deck

我不允许使用任何库。 – user2417731

在列表中找到最大元素

回答

相关问题