1

N 個の整数のシーケンスが与えられます。順列を形成する隣接する数の最長部分列の長さを見つける方法。O(N^2) アルゴリズムしか見つかりませんでした。O(NlogN) または O(N) のソリューションが必要だと思います。それらのいずれかを提案してください。

この数列の答え1 3 1 2 5は 3 (4 1 3 1 2 5 )

これは SPOJ 問題LPERMUTです。

O(N^2) アルゴリズム

Foreach i find the sum of first i elemetns: Sum(i)

Foreach i find the last element with indexes 1 .. i-1 which is equal to i-rd element: Prev(i)

Foreach i iterate j throw i+1 .. N while Prev(j) equals between i and j. 
//So we get that all elemnent between i and j are distinct. 

Then check if sum of them is equal to 1+2+...(j-i+1). 
    If it occurs that elements are permutation. 
    Sum of the elements between i and j we can get by Sum(j) - Sum(i-1)
4

1 に答える 1

-2

貪欲なアルゴリズムを使用できます

Input: ListOfElements={el_1, el_2,...,el_N}
permutation<-{}
while(dimension(size(permutation)<DesiredSize)
{
  while(VerifyIfIsPermutation(permutation U el)=false)
   el<-SelectAnElementFromList(ListOfElements)
}
print permutation

このアルゴリズムの複雑さは O(n^2) です。以前に並べ替えられた配列の場合、この複雑さを軽減できます。順列を生成する別の方法は、このリストにランダム シャッフルを使用することです。また、要素間で多数のローテーションを使用できるため、結果の順列が繰り返されないことが保証されます。

于 2012-12-30T18:48:19.260 に答える