查找具有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算法。