4

...反復手順（ハッシュテーブルなし）を使用していますか？

宿題ではありません。そして、モードとは、最も頻繁な数を意味します（統計モード）。ハッシュテーブルを繰り返し実行する方法を知りたいので、ハッシュテーブルは使用しません。

4

6 に答える 6

3

OKファンティウス、これはどうですか？

RadixSort（BucketSort）アルゴリズムを使用してリストを並べ替えます（技術的にはO（N）時間。数値は整数である必要があります）。最初の要素から開始し、その値を覚えて、1からカウントを開始します。別の値に達するまで、リストを繰り返し、カウントをインクリメントします。その値のカウントが現在の高いカウントよりも大きい場合は、その値を覚えて、モードとしてカウントします。カウントが高い場合は、両方（またはすべて）の数字を覚えておいてください。

...ええ、ええ、基数ソートはインプレースソートではないため、ハッシュテーブル（現在の数字でインデックス付けされたコレクションのコレクション）と呼ぶことができるものが含まれます。ただし、ハッシュテーブルはモードの計算ではなく、並べ替えに使用されます。

ソートされていないリストでは、ハッシュテーブルSOMEWHEREを使用せずに、線形時間でモードを計算することは不可能です。ソートされたリストでは、このアルゴリズムの後半は、現在の最大カウントを追跡するだけで機能します。

于 2010-09-22T21:19:01.453 に答える
1

確かに宿題のように聞こえます。しかし、これを試してみてください。リストを1回調べて、最大数を見つけてください。すべてゼロに初期化された、その数の要素を含む整数の配列を作成します。次に、リストをもう一度確認し、数値ごとに、配列の同等のインデックスを1ずつインクリメントします。最後に、配列をスキャンして、最も高い値を持つインデックスを返します。これはほぼ線形時間で実行されますが、ソートを含むアルゴリズムはおそらくNlogN時間以下かかります。ただし、このソリューションはメモリを大量に消費します。基本的には、そこから1つの数字を与えるためだけにベルプロットを作成します。

多くの（すべてではありませんが）言語はゼロベースの配列を使用するため、「自然数」からインデックスに変換する場合は、1を減算し、1を加算してインデックスから自然数に変換することを忘れないでください。

于 2010-09-22T20:15:41.813 に答える
1

ハッシュを使用したくない場合は、変更されたバイナリ検索トライを使用します（ノードごとにカウンターがあります）。配列内の各要素について、トライに挿入します。トライにすでに存在する場合は、カウンターを増やします。最後に、カウンターが最も高いノードを見つけます。

もちろん、カウンター変数にマップされ、同じように機能するハッシュマップを使用することもできます。反復されていないというあなたの不満を理解していません...あなたは配列を反復し、次にハッシュマップのメンバーを反復して最高のカウンターを見つけます。

于 2010-09-22T20:28:45.750 に答える
0

カウントソートを使用して、各エンティティのオカレンス数を格納する配列を調べます。h各エンティティのオカレンス数を格納します。

于 2011-12-13T17:58:42.640 に答える
0

空間と時間の複雑さが異なるPythonで2つの実装を準備しました。

1つ目は、「オカレンス配列」を使用します。これは、時間計算量の観点から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の配列が必要になります。

2番目の解決策は、モードを検索する前に入力をソートすることを前提としています。時間計算量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 に答える