Google 电面（准备二面求人品）

按我的理解写了一段可以跑通的代码 求指正！

1. public static int inferNthElement(int[] arr, int i, int n) {
   
2.                 List<Integer> items = new ArrayList<Integer>();
   
3.                 int cycle = 0;
   
4.                 int start = 0;
   
5.                 for(int j = 0; j <= n; j++) {
   
6.                         if(j == 0) items.add(arr[i]);
   
7.                         else if(!items.contains(arr[items.get(j - 1)])) {
   
8.                                 items.add(arr[items.get(j - 1)]);
   
9.                         }else {
   
10.                                 start = items.indexOf(arr[items.get(j - 1)]);
    
11.                                 cycle = j - start;
    
12.                         }
    
13.                 }
    
14.                 if(items.size() != n + 1) {
    
15.                         return items.get((n - start) % cycle + start);
    
16.                 }else {
    
17.                         return items.get(items.size() - 1);
    
18.                 }
    
19.         }

复制代码

python代码粘过来以供大家参考，多谢楼主分享。
第一个函数是k不大的时候，第二个是k可能很大的情况，考虑有环的解法。

1. def arrayIndex(A, N, k, init):
   
2.         a = init
   
3.         for i in range(1, N + 1):
   
4.                 a = A[a]
   
5. 
   
6.         return a
   
7. 
   
8. def indexCycle(A, N, k, init):
   
9.         cycle = []
   
10.         a = init
    
11.         i = 1
    
12.         while i <= N:
    
13.                 if a not in cycle:
    
14.                         cycle.append(a)
    
15.                         a = A[a]
    
16.                         i += 1
    
17.                 else:
    
18.                         break
    
19. 
    
20.         if i == N:
    
21.                 return a
    
22.         else:
    
23.                 return cycle[N % len(cycle)]

复制代码