4

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

这不是家庭作业。我所说的模式是指最常见的数字（统计模式）。我不想使用哈希表，因为我想知道如何迭代地完成它。

4

6 回答 6

3

OK Fantius，这个怎么样？

使用 RadixSort (BucketSort) 算法对列表进行排序（技术上为 O(N) 时间；数字必须是整数）。从第一个元素开始，记住它的值并从 1 开始计数。遍历列表，递增计数，直到达到不同的值。如果该值的计数高于当前的高计数，请记住该值并将计数作为模式。如果您与高计数打成平手，请记住两个（或所有）数字。

...是的，是的，RadixSort 不是就地排序，因此涉及您可以称为哈希表的东西（由当前数字索引的集合的集合）。但是，哈希表用于排序，而不是计算模式。

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

于 2010-09-22T21:19:01.453 回答
1

如果您不想使用哈希，请使用修改后的二进制搜索树（每个节点都有一个计数器）。将数组中的每个元素插入到 trie 中。如果它已经存在于 trie 中，则递增计数器。最后，找到计数器最高的节点。

当然，您也可以使用映射到计数器变量的哈希图，并且以相同的方式工作。我不明白您对它不是迭代的抱怨......您遍历数组，然后遍历哈希图的成员以找到最高的计数器。

于 2010-09-22T20:28:45.750 回答
1

绝对听起来像家庭作业。但是，试试这个：遍历列表一次，找到最大的数字。创建一个包含那么多元素的整数数组，所有元素都初始化为零。然后，再次遍历列表，对于每个数字，将数组的等效索引增加 1。最后，扫描您的数组并返回具有最高值的索引。这将在大致线性的时间内执行，而任何包含排序的算法都可能需要 NlogN 时间或更糟。然而，这个解决方案是一个内存猪。它基本上会创建一个钟形图，只是为了给你一个数字。

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

于 2010-09-22T20:15:41.813 回答
0

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

于 2011-12-13T17:58:42.640 回答
0

我在 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)
于 2013-11-09T00:29:02.440 回答
0

使用 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)
}
于 2018-02-22T17:02:13.237 回答