17

正の整数の並べ替えられていない配列が与えられた場合、並べ替えられたときに要素が連続している最長の部分配列の長さを見つけます。O(n) ソリューションを思いつきますか?

例：

{10, 5, 3, 1, 4, 2, 8, 7}、答えは 5 です。

{4, 5, 1, 5, 7, 6, 8, 4, 1}、答えは 5 です。

最初の例では、サブ配列 {5, 3, 1, 4, 2} をソートすると、最長の連続シーケンス 1,2,3,4,5 を形成できます。

2 番目の例では、サブ配列 {5, 7, 6, 8, 4} が結果のサブ配列です。

サブ配列ごとに、(最大 - 最小 + 1) がそのサブ配列の長さと等しいかどうかを確認する方法を考えることができます。真の場合、それは連続したサブ配列です。すべての中で最も長くかかります。しかし、それは O(n^2) であり、重複を処理できません。

誰かがより良い方法を教えてもらえますか?

4

7 に答える 7

1

数学的集合定義の配列Sを参照してください。

S = U j=0 k ( I j )

ここで、I jは互いに素な整数セグメントです。この数学的定義に配列を格納するために、特定の間隔ツリー (好きな赤黒ツリーまたは自己平衡ツリーに基づく :) を設計できます。ノードとツリー構造は次のようになります。

struct node {
    int d, u;
    int count;
    struct node *n_left, *n_right;
}

ここで、d は整数セグメントの下限であり、u は上限です。count配列内の重複の可能性を処理するために追加されます。ツリーに既存の要素を挿入しようとすると、何もしない代わりに、countそれが見つかったノードの値をインクリメントします。

struct root {
    struct node *root;
}

ツリーはばらばらのノードのみを格納するため、挿入は従来の赤黒ツリーの挿入よりも少し複雑です。間隔を挿入するときは、既存の間隔で潜在的なオーバーフローをスキャンする必要があります。あなたの場合、シングルトンのみを挿入するため、オーバーヘッドがあまり追加されないはずです。

3 つのノード P、L、R があり、L は P の左側の子で、R は P の右側の子です。次に、Lu < Pd および Pu < Rd を適用する必要があります (もちろん、各ノードについては d <= u)。 .

整数セグメント [x,y] を挿入する場合、「重複する」セグメント、つまり、次の不等式のいずれかを満たす間隔 [u,d] を見つける必要があります。

y >= d - 1
または
x <= u + 1

挿入された間隔がシングルトンの場合、 と のように最大 2 つの重複する間隔ノード N1とxN2 しか見つけることができません。次に、2 つの間隔と更新カウントをマージする必要があります。との間のデルタは、2 つのセグメントが互いに素になる最小のデルタであるため、次のいずれかが必要です。N1.d == x + 1N2.u == x - 1N3.d = N2.dN3.u = N1.uN3.count = N1.count + N2.count + 1N1.dN2.u

  • N1 は N2 の右側の子です
  • N2 は N1 の左の子です

したがって、挿入はO(log(n))最悪の場合でも続きます。

ここから、最初のシーケンスで順序を処理する方法を理解できませんが、興味深い結果が得られます。入力配列が完全な整数セグメントを定義する場合、ツリーにはノードが 1 つしかありません。

于 2013-04-12T12:53:14.130 に答える
1

UPD2:次の解決策は、部分配列が連続している必要がない場合の問題に対するものです。問題文を誤解していました。誰かが実際の問題に役立つ私のアイデアに基づいたアイデアを持っている可能性があるため、これを削除しません。

これが私が思いついたものです：

ディクショナリのインスタンスを作成します (ハッシュ テーブルとして実装され、通常は O(1) が与えられます)。キーは整数で、値は整数のハッシュ セットです (O(1) も) – var D = new Dictionary<int, HashSet<int>>.

配列を反復処理し、インデックス付きAの整数ごとに次のようにします。ni

  1. キーn-1とn+1が に含まれているかどうかを確認しますD。
    • どちらのキーも存在しない場合は、D.Add(n, new HashSet<int>)
    • キーの 1 つだけが存在する場合、たとえばn-1doD.Add(n, D[n-1])
    • 両方のキーが存在する場合は、D[n-1].UnionWith(D[n+1]); D[n+1] = D[n] = D[n-1];
  2. D[n].Add(n)

次に、各キーDを調べて、最大の長さのハッシュ セットを見つけます (検出の長さは O(1) です)。最大の長さが答えになります。

私の理解では、最悪の場合の複雑さは O(n*log(n)) になります。これは、UnionWith操作のためだけです。平均複雑度の計算方法はわかりませんが、O(n) に近いはずです。間違っている場合は修正してください。

UPD：コードを話すために、OPの両方の例で正しい結果を与えるC＃でのテスト実装を次に示します。

var A = new int[] {4, 5, 1, 5, 7, 6, 8, 4, 1};
var D = new Dictionary<int, HashSet<int>>();

foreach(int n in A)
{
    if(D.ContainsKey(n-1) && D.ContainsKey(n+1))
    {
        D[n-1].UnionWith(D[n+1]);
        D[n+1] = D[n] = D[n-1];
    }
    else if(D.ContainsKey(n-1))
    {
        D[n] = D[n-1];
    }
    else if(D.ContainsKey(n+1))
    {
        D[n] = D[n+1];
    }
    else if(!D.ContainsKey(n))
    {
        D.Add(n, new HashSet<int>());
    }

    D[n].Add(n);
}

int result = int.MinValue;
foreach(HashSet<int> H in D.Values)
{
    if(H.Count > result)
    {
        result = H.Count;
    }
}

Console.WriteLine(result);
于 2013-04-12T12:00:50.373 に答える
0

期待しないでください。これは部分的な回答にすぎません。

その問題は では解決できないと確信していO(n)ます。残念ながら、それを証明することはできません。

以内に解決する方法がある場合O(n^2)、解決策は次の戦略に基づいていると思います。

  1. 少なくとも要素で記述した連続部分配列が存在するかどうかO(n)を決定します。この述語を と呼びましょう。O(n log n)iE(i)
  2. i二分法を使用して、保持される最大値を見つけE(i)ます。

このアルゴリズムの合計実行時間はO(n log n)(またはO(n log^2 n)) になります。

これは、少なくとも元の定式化よりも単純になる可能性がある別の問題に問題を還元するために私が思いついた唯一の方法です。E(i)ただし、未満で計算する方法が見つからなかったO(n^2)ので、完全にオフになっている可能性があります...

于 2013-04-12T11:59:32.647 に答える
-1

ここで問題を考える別の方法があります。1 と 0 だけで構成される配列があるとします。1 が連続して最も長く続いているものを見つけたいとします。これは、1 をランレングス エンコードすることで線形時間で実行できます (0 は無視します)。元の問題をこの新しいランレングス エンコーディングの問題に変換するには、新しい配列 b[i] = (a[i] < a[i+1]) を計算します。これは明示的に行う必要はありません。一定のメモリ要件と線形の複雑さを持つアルゴリズムを実現するために暗黙的に行うことができます。

于 2013-05-01T05:47:24.300 に答える
-2

許容できる解決策は次の 3 つです。

1つ目はO(nlog(n))時間とO(n)空間、2つ目はO(n)時間とO(n)空間、3つ目はO(n)時間とO(1)空間です。

  1. を構築し、順番binary search treeにトラバースします。 最大サブセットの開始用と終了用の 2 つのポインターを保持します。ツリーを繰り返しながら値を保持します。それは時間と空間の複雑さです。
    max_sizeO(n*log(n))

  2. 線形時間でカウントソートを使用して数値セットをいつでもソートし、配列を実行できます。これは、O(n)時間と空間の複雑さを意味します。

  3. オーバーフローや大きな整数データ型がないと仮定します。配列が数学セットであると仮定します (重複する値はありません)。あなたO(1)はメモリ内でそれを行うことができます:

    • 配列の和と配列の積を計算する
    • 元のセットの最小値と最大値があると仮定して、その中にある数字を見つけます。完全にO(n)時間の複雑さです。
于 2013-04-12T11:54:31.667 に答える