2

多数要素が配列に存在する場合は true を返し、それ以外の場合は false を返すアルゴリズムを作成しようとしています。編集：2つの要素が等しいかどうかしかわかりません。つまり、< または > を使用できず、= のみを使用できます。編集：解決策は分割統治法でなければなりません。そのランタイムはnlognを超えるべきではありません.Javaで何かを書きましたが、それが正しいかどうか、ランタイムを計算する方法がわからない..ここに私が得たものがあります:

public static boolean MajorityBoolean(int[] arr) {
    int c;
    int n = arr.length;
    for (int i = 0; i < n; i = i + 2) {
        System.out.println("*");
        if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) {
            c = 0;
            for (int j = 0; j < n; j = j + 1)
                if (arr[j] == arr[i])
                    c = c + 1;
            if (c > n / 2)
                return true;
        }
    }
    return false;
}
4

3 に答える 3

5

記述されたアルゴリズムの実行時間は ですO(n^2)。外側のループがn/2回実行されるため、内側のカウンターjがリセット n/2され、内側のループが合計O(n^2)回実行されます。

あなたのアイデアの背後にあるロジックに従っているかどうかはわかりませんが、[高レベルの擬似コードで] 実装する方法を 2 つ示します。

(1)データからヒストグラムを作成します。

  • create a Map<Integer,Integer>[キーは要素、値は出現回数]
  • 配列を反復し、要素ごとに出現回数を数えます
  • ヒストグラムを反復し、一意の最大値があるかどうかを確認します。
  • ある場合は true を返し、そうでない場合は false を返します。

このアプローチは、マップとしてO(n)a を使用する場合の平均です。HashMap

(2) 最大出現回数を並べ替えて見つける:

  • 配列を並べ替えます。結果として、等しい要素はすべて互いに隣接しています。Arrays.sort(array)仕分けに使えます。
  • [ヒストグラムのアイデアと同様に] 各要素が何回出現するかを数え、一意の最大値があるかどうかを調べます。実際にはすべての要素のデータを維持する必要はありません。上位 2 つの要素を維持し、最後にそれらが同一かどうかを確認するだけで十分です。

この解決策はO(nlogn)平均 + 最悪のケースです [実際には、ソートに応じて -マージ sor t はO(nlogn)最悪のケースを示し、クイックソートはO(n^2)最悪のケースを示し、両方ともO(nlogn)平均的なケースです]。

編集：

目の前の問題を誤解していました。一意の最大値があるかどうかを見ていると思いました。これらの 2 つの解決策は問題にまだ適合します。それぞれの最後のステップを変更するだけです [最も頻繁に出現する要素が半分以上表示されるかどうかを確認します。これもかなり簡単で、 で実行可能ですO(n)]。

また、別の解決策があります。選択アルゴリズムを使用して中央値を見つけ、それを見つけた後、それが多数決要素であるかどうかを確認し、そうである場合は返します。選択アルゴリズムは分割統治ベースのソリューションであるため、ニーズに合っていると思います。

于 2012-04-14T14:23:28.797 に答える
1

サイズ n の配列 A[] の多数決要素は、n/2 回以上出現する要素です

public static boolean find(int[] arr, int size) { 
int count = 0, i, mElement;
for (i = 0; i < size; i++) {
    if (count == 0)
        mElement = arr[i];
    if (arr[i] == mElement) 
        count++;
    else
        count--;
}
count = 0;
for (i = 0; i < size; i++)
    if (arr[i] == mElement)
        count++;
if (count > size/2)
    return true;
return false;
}
于 2015-02-17T22:14:58.407 に答える
0

以下は、O(n) ソリューションです 。

于 2012-04-14T14:48:39.587 に答える