順序付けられていないnアイテムのリストがあり、そのリストで最も頻繁なアイテムを見つけようとしています。私は次のコードを書きました：
def findFrequant(L):
count = int()
half = len(L)//2
for i in L:
for j in L:
if i == j:
count += 1
if count > half:
msg = "The majority vote is {0}".format(i)
return msg
else:
continue
count = 0
return "mixed list!"
明らかに、2つのループを使用したこの手順はO(n^2)であり、同じタスクをO(n log n)時間内に実行しようとしています。私は修正やコードを書くための誰かを探しているのではなく、単に道順を探しています。
ここでは言語がわからないので、擬似コードとして扱っています。
これは、Lの同じタイプの要素のキーとintの値タイプのハッシュテーブルに依存します。ハッシュテーブル内の各レコードをカウントし、通常のmaxlistアルゴリズムを適用して、キーと値のペアの通常のコレクションとしてハッシュテーブルを繰り返します。
O（n）は線形よりわずかに悪いです。優れたハッシュの費用は線形ではなく、線形として概算される可能性があることを覚えています。使用される線形空間。
def findFrequant(L):
hash = [,]
vc = 0
vv = null
for i in L
if hash.contains(i)
hash[i] = hash[i] + 1
else
hash[i] = 1
for (k,v) in hash
if v > vc
vv = k
vc = v
else if v == vc
vv = null
if (vv == null)
return "mixed list!"
else
return "The majority vote is {0}".format(v)
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加