查找具有O（n）的時間和O（1）空間

Question

我想找到最頻繁發生的元素的列表，O(n)時間和空間O(1)最頻繁出現的元素。

首個解決方案

from collections import Counter 
def max_repetitions(elements): 
    return max([v for k, v in Counter(elements).items() if v > 1]) 

空間複雜度是O(n)。我不確定時間複雜性。是O(nlogn)還是O(n)？

解決方法二

def max_repetitions(elements): 
counter = 0 
for k, v in Counter(elements).items(): 
    if v > 1 and counter < v: 
     counter = k 
return counter 

什麼是該解決方案的時間複雜度？是O(nlogn)還是O(n)？

有沒有其他辦法？

Answer 1

在簡單的情況下，像這樣的：爲了得到時間複雜度儘量回答你多少次遍歷序列中的元素。

由於您在collections模塊中使用Counter類，它也會影響複雜性，但我們假設它是O（n）。

你做的唯一的其他工作是再次遍歷列表，也爲O（n）。這使得O（n）成爲時間複雜度，因爲它隨着元素數目n線性增長。

Answer 2

如果列表已經排序

function maxItem(list) { 
var maxCount = 0; 
var maxElement = null; 
for(var i = 0, count = 1, elm = null; i < list.length; i++) { 
    if(elm != list[i]) { 
    count = 1; 
    elm = list[i]; 
    } else { 
    count++; 
    } 
    if(count > maxCount) { 
    maxCount = count; 
    maxElement = elm; 
    } 
} 
return maxElement; 
} 

console.log(maxItem([1,1,1, 2,2,2,2, 4,4, 8,8,8,8,8])); // 8 
console.log(maxItem([1,1,1, 2,2,2,2, 4,4, 8,8,8,8,8, 9])); // 8 
console.log(maxItem([8])); // 8 

編輯對不起它。如果你想大部分元素，它是陣列中出現超過n/2倍元素的JavaScript而不是Python

Answer 3

，與O(1)空間http://www.cs.utexas.edu/~moore/best-ideas/mjrty/ 這在運行時間O(n)：您可以使用，由於博耶 - 穆爾（很簡單）MJRTY算法。