0

私はこれを解決しようとしていました: 0 から始まる連続した整数を含む並べ替えられた配列が与えられた場合 (1 つの整数が何度も繰り返される可能性があります)、たとえば - (非常に長くなる可能性もあります - これは単なる例です)、開始インデックスと終了インデックスを効率的に見つけます指定された整数の。0,0,0,1,2,3,3,3,4,4

使用を考えています

1)トラバーサル(複雑さ = O(n))

2) 修正された二分探索 (複雑さ = O(log n))。[ n = 配列全体の長さ]

次に、連続整数プロパティを利用して解決できるかどうか疑問に思っていました。別のアイデアや提案はありますか？

4

4 に答える 4

1

開始要素と終了要素を見て、配列内に要素kがいくつあるかを確認し、各境界に対して修正二分探索を実行して、要素とその左右を確認できます。O( k log( n ))より速く進むことはできないと思います。

左から右 (または右から左) の順序で境界を検索する場合、配列の小さなサブセット内を検索できるため、平均時間を短縮する必要がありますが、これが最悪の場合に影響するとは思いません-ケースの複雑さ。

つまり、0 と 1 の境界を検索して、インデックスiとその隣接要素を確認します。

|0|0|0|1|1|1|1|1|2|2|2
         \ 私 /

次に左に行きます：

|0|0|0|1|1|1|1|1|2|2|2
   \ 私 /

そして、それを見つけたので、その右側のセットで 1 と 2 の間の境界を探します。

1|1|1|1|1|2|2|2
    \ 私 /

1|1|1|1|1|2|2|2
        \ 私 /

探している境界の数がわかったので、これで完了です。

編集: 申し訳ありませんが、境界の 1 つだけが必要であることに気づきませんでした。プロセスは似ています。検索する要素 ( O(log( n )) ) を見つけてから、同じ変更された検索を使用して左右に検索し、境界を確認します。配列の全体的なサイズと配列内のアイテムの数に応じて、実際にはどちらか一方のみをチェックする方が高速になる場合があります。

于 2012-07-06T17:48:21.490 に答える
1

まず、「連続性」プロパティを無視しましょう

問題が1 つの個々の要求を処理する最も効率的な方法を見つけることに関するものである限り、単純な一般的な解決策は、2 つの連続するバイナリ検索を実行することです。順序。2 番目の検索は、配列の残りの部分、つまり、以前に検出されたシーケンスの先頭の右側で実行されます。

ただし、シーケンスの平均長が比較的小さいことが何らかの形でわかっている場合は、2 番目のバイナリ検索を線形検索に置き換えることが理にかなっています。(これは、同じような長さの 2 つの並べ替えられたシーケンスをマージするときに機能するのと同じ原理です。入力の構造により、検索のターゲットが平均してシーケンスの先頭近くに配置されることが保証されるため、線形検索はバイナリ検索よりも優れています)。

より形式的には、配列全体の長さが で、n配列内の異なる整数値の数 (多様なメトリック) がkである場合、 (実装に依存するいくつかの定数係数が実際的な関係を考え出す必要があります)。n/klog2(n)

この効果を示す極端な例はn=k、配列内のすべての値が異なる場合です。明らかに、線形検索を使用して各シーケンスの終わりを見つける (最初がわかれば) 方が、バイナリ検索を使用するよりもはるかに効率的です。

しかし、これには入力配列のプロパティに関する特別な知識が必要kです。

そして、これが「継続性」プロパティの出番です!

数値は連続しているため、配列の最後の値から配列の最初の値を引いた値は に等しくk-1、つまり、

k = array[n-1] - array[0] + 1

このルールは、元の配列の任意のサブ配列に適用して、そのサブ配列の多様性メトリックを計算することもできます。

これにより、シーケンスを見つけるための非常に実行可能で効率的なアルゴリズムが得られます。最初にシーケンスの先頭のバイナリ検索を実行し、次にとの間の関係に応じてバイナリ検索または線形検索を実行します。右サブアレイの多様性メトリックと右サブアレイの多様性メトリック)。nk

PS同じ手法を最初の検索にも適用できます。のシーケンスを探している場合、それが配列内の - 番目iのシーケンスであることがすぐにわかります。つまり、そのシーケンスの開始点の線形検索は、平均してステップを踏むことになります。この値が より小さい場合、二分探索よりも線形探索の方が適している可能性があります。jj = i - array[0]j * n/klog2(n)

于 2012-07-06T18:21:42.717 に答える
0

配列はソートされているため、二分法検索を使用できます。は配列nのサイズであり、 Aをサイズ (n/2) またはそれぞれ (n/2) と (n/2) + 1 (n が奇数の場合)Aで除算します。jの開始インデックスを探しています。(j は A にあります)A1A2

 1. if A1(n/2) < j, then you know that j is in A2. 
 2. if A2(1) > j, then you know that j is in A1. 
 3. If A2(1) = j, then j may be in A1 and A2. Just check A1(n/2).
     if A1(n/2) < j then 2. Do the same recursively on A2 to find the last index
     else apply dichotomic search to find the starting index and ending index in both arrays
于 2012-07-06T18:03:41.707 に答える
0

それはアルゴリズムでなければなりませんか？あなたの質問は位置を見つけると言っているだけですが、それが実際に何らかの形のアルゴリズム的アプローチであることが意図されている場合は、かなり標準的な方法で問題を処理する PHP 関数を提供しているのでお知らせください。

$numbers = array(0,0,0,1,2,3,3,4,4,4,4);
function get_boundaries($array,$number)
{
    $keys = array_keys($array,$number);
    $found = count($keys);
    if($found == 0)
    {
        $ret = false;
    }
    else if($found == 1)
    {
        $ret = array($keys[0],$keys[0]);
    }
    else if($found > 1)
    {
        $ret = array($keys[0],$keys[$found-1]);
    }
    return $ret;
}

$result = get_boundaries($numbers,1);
print_r($result);


//Result when looking for 0
Array
(
    [0] => 0
    [1] => 2
)

//Result when looking for 1
Array
(
    [0] => 3
    [1] => 3
)

//Result when looking for 9
(boolean) false
于 2012-07-06T18:43:59.353 に答える