在列表中找到最大元素

所以，這是我在分配中被賦予了一個問題：在列表中找到最大元素

寫一個函數，大多數（一），即在發生至少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

在列表中找到最大元素

回答

相關問題