Codility：</p> <p>Aゼロインデックス付きの配列A：最長私は本当に、私はそれについてのあなたの考えを聞きたい私をpuzzeled Codilityで最近、会社のためにテストを受けた配列

Question

内に設定され、文は次のようですN個の異なる整数からなる。配列には[0 ... N-1]の範囲のすべての整数が含まれます。 S [k] = {A [K]、A [A [K]]、A [A [A] [K]]、...}と定義する。 。

セットS [k]はkごとに有限です。

Nの整数から成る配列を与えられた

class Solution { 
    public int solution (int [] a); 
} 

関数を記述し、このアレイの最大の集合S [K]のサイズを返します。配列が空の場合、関数はOを返すはずです。 A [1] = 4、A [2] = 0、A [3] = 3、A [4] = 1、A [5] = 6、A [0] = 5、A [4] = 0、A [5] = 6、A [4] S [2] = {0,5,6,2}は4つの要素を持つので、関数は4を返すはずです。他の集合S [k]は4つ以上の要素を持たない。

まず、S [k = 2]を返す理由は分かりませんが、S [k = 0]にも4つの要素があり、最大kを返すべきではないと言われています。

O（n）スペースとランタイムでこれを行う必要があります。

アイデア？

Answer 1

まず、適切なアルゴリズム用語を使用して問題を再現する必要があります。整数0〜N-1の配列は、N個の要素の置換である。 このようなセットはサイクルです。各置換は1サイクル以上で構築されます。 各要素は正確に1サイクルの一部です（異なる名前でサイクルをアドレス指定できますが、同じ要素と同じサイクルです）。 名前が示すようにサイクルはサイクルであり、要素から始まり、その要素の番号の位置に移動し、開始位置で終わることが保証されています。これはまた、Sの有限サイズを保証することができる理由であり、問​​題のステートメントで実際には必要ではありません。ヒントです。

単純なアルゴリズムは、例えば次のようになります。

1. が
2. は、あなたが再びEに到達するまでeから始まるサイクルトラバース
3. P
外の要素eを取る集合P内のすべての要素を入れて、必要に応じて、周期の大きさをカウントPから各要素を削除
4. 更新最大サイクルサイズが見つかり
5. Pリピートに残された任意の要素、ステップのある場合2.
6. 最大サイクルが返されます。 （N）O、O（n）のセットP. 時間複雑度は、各要素が一度だけPから除去される

空間複雑そう