4

さらに別のインタビューの質問では、可能な限り短い計算時間でソートされた配列が与えられた場合に、繰り返される値の可能な最大のサブ配列を見つけるように求められました。

Let input array be A[1 ... n]
Find an array B of consecutive integers in A such that:
for x in range(len(B)-1):
     B[x] == B[x+1]

最良のアルゴリズムは、配列を半分に分割し、中央から外側に向かって整数を相互に比較し、中央から同じ整数の最長のひずみを見つけることだと思います。次に、配列を半分に分割し、2つの半分でメソッドを呼び出すことにより、メソッドを再帰的に呼び出します。

私のインタビュアーは私のアルゴリズムは良いと言いましたが、アルゴリズムがO（logn）であるという私の分析は正しくありませんが、正解が何であるかを教えてくれませんでした。私の最初の質問は、このアルゴリズムのBig-O分析とは何ですか？（できるだけ多くの作業を見せてください！Big-Oは私の得意ではありません。）そして、私の2番目の質問は、もっと時間効率の良いアルゴリズムがあるかどうかという私の好奇心のためだけです。

4

4 に答える 4

4

この問題に対して実行できる最善の方法はO(n)解決策であるため、アルゴリズムが正しく、との両方である可能性はありませんO(lg n)。

たとえば、配列に繰り返し要素が含まれていない場合を考えてみます。これを決定するには、すべての要素を調べる必要があり、すべての要素を調べることはO(n)です。

これは、繰り返される要素の最長のサブシーケンスを見つける単純なアルゴリズムです。

start = end = 0
maxLength = 0
i = 0
while i + maxLength < a.length:
    if a[i] == a[i + maxLength]:
        while i + maxLength < a.length and a[i] == a[i + maxLength]:
            maxLength += 1
        start = i
        end = i + maxLength
    i += maxLength

return a[start:end]

サブシーケンスが長くなると考える理由がある場合は、の初期値をヒューリスティックに選択された値に設定して処理を高速化し、シーケンスが見つからない場合（つまり、後にmaxLengthなってしまう場合）にのみ短いシーケンスを探すことができます。end == 0最初のパス。）

于 2012-09-15T14:07:50.517 に答える
0

Aすべてが一意であるか、すべてが同じである最悪のシナリオでAは、配列内のすべての要素を調べて、重複がないか、すべての配列に1つの数値が含まれていることを確認する必要があることに同意します。他のポスターが言っているように、それはそうなるでしょうO(N)。分割統治法がこのアルゴリズムの複雑さを大幅に改善するのに役立つかどうかはわかりませんが、再帰を使用することでコードを少し単純化できる可能性があります。分割統治法は、入力の大部分を破棄できる場合（たとえば、バイナリ検索）にBig Oを削減するのに役立ちますが、すべての入力を調べる必要がある可能性がある場合は、それほど違いはありません。

ここでの結果は、見つけた最大のBのサイズを返すだけだと思いますが、代わりにBを返すようにこれを簡単に変更できます。

したがって、アルゴリズムの面では、Aがソートされていることを考えると、配列を順番にウォークスルーするよりも速く/簡単な答えが得られるかどうかはわかりません。最も簡単な答えは、2つのポインターを用意することです。1つはインデックス0から始まり、もう1つはインデックス1から始まります。それらを比較してから両方をインクリメントします。それらが同じであるたびに、カウンターを上向きにチェックして現在のサイズを示しB、それらが異なる場合は、そのカウンターをゼロにリセットします。また、これまでに見つけたBの最大サイズの変数を保持し、より大きなBを見つけるたびにそれを更新しますB。

于 2012-09-15T14:38:40.420 に答える
0

このアルゴリズムでnは、訪問された要素ごとに一定数の計算で要素が訪問されるため、実行時間はO(n)です。

与えられたソートされた配列A[1..n]：

max_start = max_end = 1
max_length = 1
start = end = 1
while start < n
    while A[start] == A[end] && end < n
        end++
    if end - start > max_length
        max_start = start
        max_end = end - 1
        max_length = end - start
    start = end
于 2012-09-15T14:42:03.110 に答える
-1

連続する最長の整数が長さ1のみであると仮定すると、n個のアイテムの配列A全体をスキャンすることになります。したがって、複雑さはnではなく、len（B）の観点からです。

複雑さがO（n / len（B））かどうかわからない。

2エッジケースの確認

-n == len（B）の場合、即座に結果が得られます（A[0]とA[n-1]のみをチェックします）。 -n == 1の場合、すべての要素をチェックしてO（n）を取得します-通常の場合、分析するアルゴリズムを書くのが面倒です...

編集

len(B)それが事前にわからないことを考えると、最悪の場合、つまりO（n）をとらなければなりません。

于 2012-09-15T14:06:39.433 に答える