47

このインタビューの質問を見つけましたが、O(N^2 * P) より優れたアルゴリズムを思いつきませんでした:

P 個の自然数 (1,2,3,...,P) のベクトルと、要素が最初のベクトルからのものである長さ N の別のベクトルが与えられた場合、すべての要素が均一に分布するように、2 番目のベクトルで最長の部分列を見つけます。 （周波数は同じです）。

例 : (1,2,3) および (1, 2,1,3,2,1,3,1,2,3 ,1)。最長のサブシーケンスは区間 [2,10] にあります。これは、同じ頻度 (1 が 3 回、2 が 3 回、3 が 3 回) の最初のシーケンスのすべての要素が含まれているためです。

時間計算量は O(N * P) である必要があります。

4

5 に答える 5

49

「サブシーケンス」は通常、不連続を意味します。あなたが「サブリスト」を意味していると仮定します。

これは、ハッシュできると仮定した O(NP) アルゴリズムです(仮定は不要です。代わりに基数ソートを使用できます)。各数値の現在の合計を保持する配列をスキャンします。あなたの例では、

  1  2  3
 --------
  0  0  0
1 
  1  0  0
2
  1  1  0
1
  2  1  0
3
  2  1  1
2
  2  2  1
1
  3  2  1
3
  3  2  2
1
  4  2  2
2
  4  3  2
3
  4  3  3
1
  5  3  3

次に、最小要素を減算して各行を正規化します。結果は

 0: 000
 1: 100
 2: 110
 3: 210
 4: 100
 5: 110
 6: 210
 7: 100
 8: 200
 9: 210
10: 100
11: 200.

2 つのハッシュを準備し、各行を最初に表示されるインデックスと最後に表示されるインデックスにマッピングします。キーを反復処理し、最後から最初に最大のものを取得します。

000: first is at 0, last is at 0
100: first is at 1, last is at 10
110: first is at 2, last is at 5
210: first is at 3, last is at 9
200: first is at 8, last is at 11

サブリストの長さが 9 であるため、最適なキーは 100 です。サブリストは (1+1) 番目の要素から 10 番目の要素です。

これは、最初と最後の正規化されていないヒストグラムが定数を追加するまで同じである場合にのみ、サブリストのバランスが取れているためです。これは、最初と最後の正規化されたヒストグラムが同一である場合にのみ発生します。

于 2012-04-17T14:09:46.410 に答える
6

メモリ使用量が重要でない場合は、簡単です...

行列の次元を指定し、列(i)に、 (i) 2 番目のベクトルの最初の要素の間にある要素の数に対応する値N*pを保存できます...p

i行列を完成させた後、列のすべての要素が異なっていない列を検索できますi。最大iが答えです。

于 2012-04-17T14:21:09.667 に答える
3

ランダム化により、線形時間まで下げることができます。アイデアは、整数の合計がゼロになるように、各 P 値をランダムな整数に置き換えることです。次に、等しい 2 つのプレフィックスの合計を探します。これにより、出力を確認することで修正できる誤検知の可能性がわずかに生じます。

Python 2.7 では:

# input:
vec1 = [1, 2, 3]
P = len(vec1)
vec2 = [1, 2, 1, 3, 2, 1, 3, 1, 2, 3, 1]
N = len(vec2)
# Choose big enough integer B.  For each k in vec1, choose
# a random mod-B remainder r[k], so their mod-B sum is 0.
# Any P-1 of these remainders are independent.
import random
B = N*N*N
r = dict((k, random.randint(0,B-1)) for k in vec1)
s = sum(r.values())%B
r[vec1[0]] = (r[vec1[0]]+B-s)%B
assert sum(r.values())%B == 0
# For 0<=i<=N, let vec3[i] be mod-B sum of r[vec2[j]], for j<i.
vec3 = [0] * (N+1)
for i in range(1,N+1):
    vec3[i] = (vec3[i-1] + r[vec2[i-1]]) % B
# Find pair (i,j) so vec3[i]==vec3[j], and j-i is as large as possible.
# This is either a solution (subsequence vec2[i:j] is uniform) or a false
# positive.  The expected number of false positives is < N*N/(2*B) < 1/N.
(i, j)=(0, 0)
first = {}
for k in range(N+1):
    v = vec3[k]
    if v in first:
        if k-first[v] > j-i:
            (i, j) = (first[v], k)
    else:
        first[v] = k
# output:
print "Found subsequence from", i, "(inclusive) to", j, "(exclusive):"
print vec2[i:j]
print "This is either uniform, or rarely, it is a false positive."
于 2012-04-19T05:14:07.090 に答える
2

Pここに観察があります。長さの乗算ではない均一に分散されたシーケンスを取得することはできません。NこれはP、 、2P、3P...であるサブシーケンスのみをチェックする必要があることを意味します-(N/P)^2そのようなシーケンス。

于 2012-04-17T14:18:33.243 に答える
0

uty のソリューションを強化することで、P に依存せずに、これを O(N) 時間まで下げることができます。

行ごとに、各要素の正規化されたカウントを格納する代わりに、現在のインデックスの正規化されたカウントのみを保持しながら、正規化されたカウントのハッシュを格納します。各反復中に、最初に正規化されたカウントを更新する必要があります。これは、カウントがインクリメントされるときにカウントの各デクリメントが支払われる場合、O(1) の償却コストを持ちます。次に、ハッシュを再計算します。ここで重要なのは、ハッシュされるタプルの要素の 1 つが増加または減少した後、ハッシュを簡単に更新できる必要があるということです。

このハッシュを効率的に行う方法の少なくとも 1 つが、この質問への回答に示されています。指数関数を計算してハッシュに追加する量を決定するための O(lg P) コストは、事前計算の総実行時間 O(P) で素数を法とする指数関数を事前計算することによって除去できることに注意してください。 O(N + P) = O(N) の実行時間。

于 2012-04-25T21:35:18.740 に答える