コーディングテストJava配列S = A [A [A [A]]]]？

Question

私は通常の配列 'A'を与え、次のような計算を実行するように要求されたコーディングテストを試みました：x = A[i], x = A[A[i]], x = A[A[A[i]]] ....（詳細は画像で詳しく説明します）。質問配列A = [5,4,0,3,1,6,2] and A[2] = 0, A[A[i]] = 4, A[A[A[i]]] = 6, A[A[A[A[i]]]] = 2に示されている例では、

誰かがこの背後にある論理を説明し、問題に対する独自の解決策を示すことができます。

codilityテストは

P.S.をsnipet私はサンプルテストを完了して渡すことができましたが、私はポイントを得ることができない本当に安い方法を使用したと感じます。

以下のコードは私の解決策でしたが、うまくいきましたが、それを作った人が探していたものではないと私は思います。私は "A [A [A ....]"の背後にある論理を理解できませんでした。

class Solution { 
    public int solution(int[] A) { 
     // write your code in Java SE 8 

     String[] values = new String[A.length]; 

     int max = 0; 
     int counter = 0; 

     for(int i = 0; i < A.length; i++){ 

     String ASet1 = Integer.toString(A[i]); 
     String ASet2 = Integer.toString(A[A[i]]); 
     String ASet3 = Integer.toString(A[A[A[i]]]); 
     String ASet4 = Integer.toString(A[A[A[A[i]]]]); 
     String ASet5 = Integer.toString(A[A[A[A[A[i]]]]]); 
     String ASet6 = Integer.toString(A[A[A[A[A[A[i]]]]]]); 
     String ASet7 = Integer.toString(A[A[A[A[A[A[A[i]]]]]]]); 
     String ASet8 = Integer.toString(A[A[A[A[A[A[A[A[i]]]]]]]]); 
     String ASet9 = Integer.toString(A[A[A[A[A[A[A[A[A[i]]]]]]]]]); 

      values[i] = ASet1 + ASet2 + ASet3 + ASet4 + ASet5 + ASet6 + ASet7 + ASet8 + ASet9; 

      //System.out.println(values[i]); 
      } 



     for(int l = 0; l < values.length; l++){ 
     String valueline = values[l]; 
     for(int j = 0; j < values.length; j++){ 


      counter = 0; 
      char c = valueline.charAt(j); 

      for(int k = 1; k < values.length; k++){ 
      char c2 = valueline.charAt(k); 


      if(c != c2){ 

      counter++; 

      }else{ 
       continue; 
       //counter = 0; 
       } 

      if(max < counter){ 
       max = counter; 
       } 
     } 

     } 
     } 

     return max - 1; 
    } 
} 

Answer 1

置換の最長分割サイクルの長さを見つける必要があります。 ASetXXXがデッドエンドで接近することは明らかです。条件ループを使用してジャンプが同じポイントに戻るタイミングを判断するだけです。

i = startidx 
    do 
    i = A[i] 
    while (i != startidx) 

startidxのすべてに対してこの操作を行います。

マークは、私はそれが答えですけど、私は仕事を自分で解決することが面白かったとして、なぜここに私の解決策を投稿しないように、過度な作業に

Answer 2

を避けるために、インデックスを使用していました。

アイデアは元の配列の内側に配列の長さを設定することです（タスクの説明でこれが可能です）。

Set要素を訪れている間、Setでは値は負の符号で置き換えられます。基本的には、単に値を-1の定数に置き換えることができます。

1つのセットが訪問されるとすぐに別のセットに移動します。

時間の複雑さは線形です。 ストレージの複雑さは一定です。 C++での

ソリューション：

#include <iostream> 
#include <string> 
#include <stack> 
#include <vector> 

int solve(std::vector<int>& i_arr) 
{ 
    int ret = 0; 
    for (int i = 0, sz = i_arr.size(); i < sz; ++i) // sequences beginnings searching loop 
    { 
     if (i_arr[i] < 0) // already visited, thus not the sequence beginning 
      continue; 
     for (int j = i, c = 0;;) // sequence elements iteration loop 
     { 
      int val = i_arr[j]; 
      if (val >= 0) // not the sequence end, continue sequence iteration 
      {     
       i_arr[j] = --c; // replacing value with order in sequence but negative 
       j = val; // moving to the next element in sequence 
      } 
      else // sequence end reached, looping back... 
      { 
       if (c < ret) // detecting longest sequence 
        ret = c; 
       break; // current sequence end reached, breaking 
      } 
     } 
    } 
    return -ret; 
} 

int main() 
{ 
    std::vector<int> arr{5,4,0,3,1,6,2}; 
    std::cout << solve(arr) << std::endl; 
    for (const auto& e : arr) 
     std::cout << e << ' '; 
    return 0; 
} 

出力は、（第2行は配列が変更されたか、元のアイデアを提供します）のように見える方法は次のとおりです。

4 
-1 -1 -4 -1 -2 -2 -3