-1

これは宿題です。

配列のモード (正の値) を見つけ、モードがsizeof(array)/2支配的な値より大きい場合は、その値を二次的に返す必要があります。一部の配列にはどちらもありません。これは簡単ですが、決定の前に配列をソートしてはならないという制約があり、さらに、複雑さは O(nlogn) のオーダーでなければなりません。

この 2 番目の制約とマスター定理を使用して、時間計算量 'T(n) = A*T(n/B) + n^D' を決定できます。ここで、A=B および log_B(A)=D for O(nlogn ） 真であります。したがって、A=B=D=2 です。ドミナント値は、配列の前半、後半、または両方でドミナントでなければならないため、これも便利です。

'T(n) = A*T(n/B) + n^D' を使用すると、検索関数が各レベル (A) で 2 回自身を呼び出し、各レベル (B) で問題セットを 2 で分割することがわかります。アルゴリズムが各レベルで n^2 を考慮に入れる方法を考え出すのに行き詰まっています。

これのいくつかのコードを作成するには：

int search(a,b) {
    search(a, a+(b-a)/2);
    search(a+(b-a)/2+1, b);
}

ここで欠けている「接着剤」は、これらの分割された機能を組み合わせる方法であり、n^2 の複雑さを実装すると思います。ここには、前半または後半、またはその両方でドミナントがドミナントでなければならないいくつかのトリックがありますが、複雑さの制約で今それがどのように役立つかはよくわかりません.

小さな配列の例をいくつか書き留め、それが分割される方法を示しました。常に優勢な値を返す単一のメソッドを見つけるという正しい方向に進むことができないようです。

レベル 0 では、関数は自分自身を呼び出して配列の前半と後半を検索する必要があります。それは再帰して、それ自体を呼び出す必要があります。次に、各レベルで n^2 操作を実行する必要があります。したがって、配列 [2,0,2,0,2] では、それを [2,0] での検索と [2,0,2] での検索に分割し、さらに 25 回の操作を実行します。[2,0] の検索は、[2] の検索と [0] の検索を呼び出し、4 つの操作を実行します。これらは配列空間自体の検索である必要があると思います。私は C++ を使用し、STL から何かを使用して値を繰り返しカウントすることを計画していました。大きな配列を作成し、そのインデックスでカウントを更新するだけです。

4

2 に答える 2

2

配列のドミナント モードだけを見つけて再帰的に実行する場合は、次の擬似コードを使用します。

def DominantMode(array):
    # if there is only one element, that's the dominant mode
    if len(array) == 1: return array[0]
    # otherwise, find the dominant mode of the left and right halves
    left = DominantMode(array[0:len(array)/2])
    right = DominantMode(array[len(array)/2:len(array)])
    # if both sides have the same dominant mode, the whole array has that mode
    if left == right: return left
    # otherwise, we have to scan the whole array to determine which one wins
    leftCount = sum(element == left for element in array)
    rightCount = sum(element == right for element in array)
    if leftCount > len(array) / 2: return left
    if rightCount > len(array) / 2: return right
    # if neither wins, just return None
    return None

上記のアルゴリズムは O(nlogn) 時間ですが、O(logn) スペースしかありません。

配列のモード (ドミナント モードだけでなく) を見つけたい場合は、まずヒストグラムを計算します。要素値をその頻度にマップするハッシュ テーブルにヒストグラムを格納することにより、O(n) 時間 (配列の各要素を 1 回だけ参照) でこれを行うことができます。

ヒストグラムが計算されたら、それを反復処理して (各要素を最大 1 回訪問する)、最高度数を見つけることができます。配列のサイズの半分を超える頻度が見つかったら、すぐに戻り、残りのヒストグラムを無視できます。ヒストグラムのサイズは元の配列のサイズを超えることはできないため、このステップも O(n) 時間 (および O(n) スペース) になります。

両方のステップが O(n) 時間であるため、結果のアルゴリズムの複雑さは O(n) 時間になります。

于 2013-02-07T05:32:35.733 に答える
2

いくつかの数が半分以上発生する場合、次のように O(n) 時間の複雑さと O(1) の空間複雑さによって実行できます。

int num = a[0], occ = 1;
for (int i=1; i<n; i++) {
    if (a[i] == num) occ++;
    else {
        occ--;
        if (occ < 0) {
            num = a[i];
            occ = 1;
        }
    }
}

そのような数が発生するかどうかわからないので、最初に上記のアルゴリズムを適用して数値を取得し、次に配列全体を 2 回繰り返して数値の発生を取得し、それが半分より大きいかどうかを確認するだけです。

于 2013-02-07T06:20:00.743 に答える