6

2 つの入力配列 X と Y があります。配列 Y で最も高い頻度で発生する配列 X の要素を返したいと考えています。

これを行う単純な方法では、配列 X の各要素 x に対して、配列 Y の出現回数を直線的に検索し、最も頻度の高い要素 x を返す必要があります。疑似アルゴリズムは次のとおりです。

 max_frequency = 0
 max_x = -1             // -1 indicates no element found
 For each x in X
     frequency = 0
     For each y in Y
         if y == x
             frequency++
     End For
     If frequency > max_frequency
         max_frequency = frequency
         max_x = x
     End If
 End For
 return max_x

ネストされたループが 2 つあるため、このアルゴリズムの時間計算量は O(n^2) になります。O(nlogn) 以上でこれを行うことはできますか?

4

8 に答える 8

7

キーをカウントにマッピングするハッシュ テーブルを使用します。配列内の各要素に対して、 likecounts[element] = counts[element] + 1またはお使いの言語の同等の操作を行います。

最後に、ハッシュ テーブルのマッピングをループし、最大値を見つけます。

于 2013-03-23T21:16:34.227 に答える
3

または、追加のデータ構造を持つことができる場合は、配列Yをウォークし、数値ごとにハッシュテーブルの頻度を更新します。これにはO(N(Y)時間がかかります。次に、Xを歩き、Xのどの要素が最も頻度が高いかを見つけます。これにはO(N(X))時間がかかります。全体：線形時間、および両方の各要素XとY任意の実装を少なくとも1回確認する必要があるため（編集： jwpat7が指摘しているように、これはすべての場合/すべての実装で厳密に言えば真実ではありませんが、最悪の場合は真実ですケース）、それより速くそれを行うことはできません。

于 2013-03-23T21:16:38.103 に答える
2

一般的なアルゴリズムの時間計算量を以下に示します。

Algorithm     |   Best    |   Worst   |  Average
--------------+-----------+-----------+---------- 
MergeSort     | O(n lg n) | O(n lg n) | O(n lg n)  
InsertionSort |   O(n)    |  O(n^2)   |  O(n^2)  
QuickSort     | O(n lg n) |  O(n^2)   | O(n lg n)  
HeapSort      | O(n lg n) | O(n lg n) | O(n lg n)  
BinarySearch  |   O(1)    |  O(lg n)  |  O(lg n)

一般に、特定の基準を満たすためにリストをトラバースする場合、線形時間よりも優れた方法はありません。配列を並べ替える必要がある場合は、Mergesort（非常に信頼できる）を使用して、配列内で最も頻度の高い要素を見つけます。

注：これは、並べ替えアルゴリズムを使用することを前提としています。それ以外の場合、任意のデータ構造を使用できる場合は、ルックアップ時間が一定のハッシュマップ/ハッシュテーブルタイプの構造を使用します。このようにして、キーを照合し、頻度のキーと値のペアを更新するだけです。お役に立てれば。

于 2013-03-23T21:17:37.013 に答える
2

第 1 ステップ: XとYの両方を並べ替えます。対応する長さをmとnとすると、このステップの複雑さは になります O(n log n) + O(m log m)。

2 番目のステップ: Yの各X i をカウントし、これまでの最大カウントを追跡します。ソートされたYにおけるX iの検索は です。2 番目のステップの合計の複雑さは次のとおりです。O(log n)O(m log n)

全体の複雑さ: O(n log n) + O(m log m) + O(m log n)、または簡略化:O(max(n,m) log n)

于 2013-03-24T05:40:16.880 に答える
1

両方のリストの長さがnの場合、推奨されるアプローチはO（n ^ 2）になります。より可能性が高いのは、リストの長さが異なる可能性があるため、時間計算量はO（mn）として表すことができるということです。

問題を2つのフェーズに分けることができます。1。頻度でYから一意の要素を並べ替えます。2。Xに存在するこのリストから最初のアイテムを見つけます。

これは宿題の質問のように聞こえるので、これらの個々のステップをどれだけ速く実行できるかを考えさせます。これらのコストの合計は、アルゴリズムの全体的なコストになります。あなたが現在持っている2つのリストの長さの積よりも安くなる多くのアプローチがあります。

于 2013-03-23T21:19:16.727 に答える
1

分割統治法に基づくマージソートは、O（nlogn）の複雑さをもたらします

于 2013-03-23T21:13:55.987 に答える
1

X と Y を並べ替えます。次にマージ並べ替えを行います。X で同じ要素に遭遇するたびに、Y からの頻度をカウントします。

複雑なので、O(nlogn) + O(mlogm) + O(m+n) = O(klogk) ここで、n,m = X、Y の長さ。k = 最大(m,n)

于 2013-07-24T13:29:50.710 に答える
0

クイックソートを実行してから、行にある数値の数+その数値をカウントする変数を使用してそれをトラバースできます。それはあなたにnlognを与えるはずです

于 2013-03-23T21:13:08.760 に答える