如何在O(N)时间复杂度内计算未排序整数数组的众数？

Question

...使用迭代过程（无哈希表）？

这不是作业。通过模式，我指的是最常见的数字（统计模式）。我不想使用哈希表，因为我想知道如何通过迭代实现。

- user455497

---

看起来像是作业。试着去做一下，展示你的代码。 - egrunin

为什么不能使用哈希表？ - Heinzi

https://dev59.com/IG865IYBdhLWcg3wlvqq 这个问题是相关的，但是只有当最常见的元素出现次数 > n/2 时，算法才能保证有效。 - dave

不可能！“哈希表”是一个广泛的术语。我认为任何执行此操作的算法都可以被证明采用了（也许是复杂的）哈希表类型。 - Fantius

我认为Fantius是正确的。线性计算一系列的众数涉及到多值计数，并且您必须以某种方式存储每个计数。即使您将其隐藏在查询语言后面，其背后的实现也会回归到迭代元素并对其进行计数。 - KeithS

如果这不是作业，你怎么知道可能的解决方案存在呢？ - Mark Ransom

Answer 1

好的，Fantius，这个怎么样？

使用基数排序（桶排序）算法对列表进行排序（技术上是O（N）时间；数字必须为整数）。从第一个元素开始，记住它的值并开始计数为1。遍历列表，递增计数，直到达到不同的值。如果该值的计数高于当前最高计数，则将该值和计数记为众数。如果与最高计数相等，则记住两个（或所有）数字。

…是的，是的，基数排序不是原地排序，因此涉及到一些可以称之为哈希表的东西（由当前数字索引的集合）。但是，哈希表用于排序，而不是用于计算模式。

我要说，在未排序的列表上，如果不涉及哈希表，则无法在线性时间内计算模式。在排序列表上，该算法的后半部分通过仅跟踪当前最大计数来工作。

- KeithS

Answer 2

听起来肯定是作业。但是，试试这个：先遍历一次列表，找到最大的数字。创建一个整数数组，其元素数量为该数字，全部初始化为零。然后再次遍历列表，对于每个数字，将相应索引的数组加1。最后，扫描数组并返回具有最高值的索引。这将在大约线性时间内执行，而包括排序的任何算法可能需要NlogN时间或更长时间。但是，这种解决方案会占用大量内存；它基本上会创建一个钟形图，只为给您提供一个数字。

请记住，许多（但不是所有）语言使用从零开始的数组，因此在从“自然”数字转换为索引时，要减去一，然后再加一以从索引转换为自然数字。

- KeithS

---

你的整数数组实际上是一个带有完美哈希的哈希表。 - Fantius

Answer 3

如果您不想使用哈希表，可以使用修改后的二分搜索字典树（每个节点带有计数器）。对于数组中的每个元素，都将其插入到字典树中。如果它已经存在于字典树中，则增加计数器。最后，找到具有最高计数器的节点。

当然，您也可以使用哈希映射到计数器变量，这样也可以达到相同的效果。我不明白您对它不是迭代的抱怨...您遍历数组，然后遍历哈希映射的成员以查找最高计数器。

- patros

---

我认为这些想法也违反了“无哈希表”要求。 - Fantius

Answer 4

使用JavaScript：

const mode = (arr) => {
    let numMapping = {};
    let mode
    let greatestFreq = 0;
    for(var i = 0; i < arr.length; i++){
        if(numMapping[arr[i]] === undefined){
            numMapping[arr[i]] = 0;
        }
        numMapping[arr[i]] += 1;
        if (numMapping[arr[i]] > greatestFreq){
          greatestFreq = numMapping[arr[i]]
          mode = arr[i]
        }
    }
    return parseInt(mode)
}

- Mr Mode

Answer 5

我用Python准备了两个不同空间和时间复杂度的实现：

第一个实现使用“出现数组”，在时间复杂度上为O(k)，在所需空间上为S(k+1)，其中k是输入中最大的数字。

input =[1,2,3,8,4,6,1,3,7,9,6,1,9]

def find_max(tab):
    max=tab[0]
    for i in range(0,len(tab)):
        if tab[i] > max:
            max=tab[i]
    return max

C = [0]*(find_max(input)+1)
print len(C)
def count_occurences(tab):
    max_occurence=C[0]
    max_occurence_index=0
    for i in range(0,len(tab)):
        C[tab[i]]=C[tab[i]]+1
        if C[tab[i]]>max_occurence:
            max_occurence = C[tab[i]]
            max_occurence_index=tab[i]
    return max_occurence_index

print count_occurences(input)

注意：想象一下这样一个可怜的输入例子，比如一个数组[1, 10^8,1,1,1]，那么需要一个长度为k+1=100000001的数组。

第二个解决方案假设我们在搜索众数之前对输入进行排序。我使用了基数排序，其时间复杂度为O(kn)，其中k是最长数字的长度，n是输入数组的大小。然后我们必须迭代整个已排序的大小为n的数组，以确定表示模式的最长数字子集。

input =[1,2,3,8,4,6,1,3,7,9,6,1,9]

def radix_sort(A):
    len_A = len(A)
    mod = 5 #init num of buckets
    div = 1
    while True:
        the_buckets =  [[], [], [], [], [], [], [], [], [], []]
        for value in A:
            ldigit = value % mod
            ldigit = ldigit / div
            the_buckets[ldigit].append(value)
        mod = mod * 10
        div = div * 10
        if len(the_buckets[0]) == len_A:
            return the_buckets[0]
        A = []
        rd_list_append = A.append
        for b in the_buckets:
            for i in b:
                rd_list_append(i)     

def find_mode_in_sorted(A):
    mode=A[0]
    number_of_occurences =1
    number_of_occurences_canidate=0
    for i in range(1,len(A)):
        if A[i] == mode:
            number_of_occurences =number_of_occurences +1
        else:
            number_of_occurences_canidate=number_of_occurences_canidate+1
        if A[i] != A[i-1]:
            number_of_occurences_canidate=0
        if number_of_occurences_canidate > number_of_occurences :
            mode=A[i]
            number_of_occurences =number_of_occurences_canidate+1
    return mode#,number_of_occurences 

s_input=radix_sort(input)
print find_mode_in_sorted(s_input)

- andilabs

Answer 6

只需使用计数排序并查看存储每个实体的数字出现次数的数组即可。h存储每个实体的数字出现次数。

- Ali Hassan