请问下这道题除了while loop的方法，有啥更高效的解法么？

Passing Yearbooks
There are n students, numbered from 1 to n, each with their own yearbook. They would like to pass their yearbooks around and get them signed by other students.
You're given a list of n integers arr[1..n], which is guaranteed to be a permutation of 1..n (in other words, it includes the integers from 1 to n exactly once each, in some order). The meaning of this list is described below.
Initially, each student is holding their own yearbook. The students will then repeat the following two steps each minute: Each student i will first sign the yearbook that they're currently holding (which may either belong to themselves or to another student), and then they'll pass it to student arr[i-1]. It's possible that arr[i-1] = i for any given i, in which case student i will pass their yearbook back to themselves. Once a student has received their own yearbook back, they will hold on to it and no longer participate in the passing process.
It's guaranteed that, for any possible valid input, each student will eventually receive their own yearbook back and will never end up holding more than one yearbook at a time.
You must compute a list of n integers output, whose element at i-1 is equal to the number of signatures that will be present in student i's yearbook once they receive it back.
Signature
int[] findSignatureCounts(int[] arr)
Input
n is in the range [1, 100,000].
Each value arr[i] is in the range [1, n], and all values in arr[i] are distinct.
Output
Return a list of n integers output, as described above.
Example 1
n = 2
arr = [2, 1]
output = [2, 2]
Pass 1:
Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is Student 2.
Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is Student 1.
Pass 2:
Student 1 signs Student 2's yearbook. Then they pass it to the student at arr[0], which is Student 2.
Student 2 signs Student 1's yearbook. Then they pass it to the student at arr[1], which is Student 1.
Pass 3:
Both students now hold their own yearbook, so the process is complete.
Each student received 2 signatures.

不清楚楼主说的while loop方法是什么方法，可能是brute force的意思。。
这个题可以这样想，一个yearbook它从本人手上离开，经过一些学生的手，回到本人手上。签字的数量就是这些人的count.
比如一开始的input是 [1,3,4,5,2], 看yearbook 3 的旅程就是(括号里是index) 3(1) -> 4(2) -> 5(3) -> 2(4) -> 3(1), 一共4人签字。
那么如果看yearbook 5 的旅程 5(3) -> 2(4) -> 3(1) -> 4(2) -> 5(3) 也是4人签字。
你会发现它其实走的圈和yearbook 3 是一样的，可以总结，yearbook 3, 4, 5, 2 都走的是一个圈，都是4个签字。
所以我们就从input array开始扫，对每个element进行走圈，并记录见过的yearbook.
比如我们看 3(1)的时候，所有走过的student 4,5,2,都存在一个visted里面，后面Input array里碰到就不用看了(因为我们已经知道4,5,2被签次数和3一样)。然后存下 yearbook 3 被签了 4次的信息，再存下 yearkbook 4，5，2被签的次数和yearbook 3相同的信息。
结束以后就能得出[1,4,4,4,4]

cloudero 发表于 2021-9-4 23:48
不清楚楼主说的while loop方法是什么方法，可能是brute force的意思。。
这个题可以这样想，一个yearbook ...

非常感谢你的回复。我之前说的while loop就是brute force的solution。我的确没想到可以预先存起来。感觉memorization是一个很常用的技巧。经常忘了。根据你提供的思路，我写了下代码，如下。能帮忙看下，这个代码是不是正确吗？或者还有啥改进的地方吗？时间复杂度应该是O(n)

1. def findSignatureCounts(arr):
   
2.   # Write your code here
   
3.   
   
4.   n = len(arr)
   
5.   
   
6.   result = [0 for i in range(n)]
   
7.   
   
8.   
   
9.   for i in range(1, n+1):
   
10.     if result[i-1] > 0:
    
11.         continue
    
12.         
    
13.     cnt_i = 1
    
14.    
    
15.     j = i
    
16.    
    
17.     visited_val = set()
    
18.    
    
19.     while arr[j-1] != i:
    
20.       cnt_i += 1
    
21.       j = arr[j-1]
    
22.       if result[j-1] > 0:
    
23.         cnt_i = result[j-1]
    
24.         break
    
25.       else:
    
26.         visited_val.add(j)
    
27.   
    
28.     result[i-1] = cnt_i
    
29.    
    
30.     if len(visited_val):
    
31.       for k in visited_val:
    
32.         result[k-1] = cnt_i
    
33.    
    
34.   return result

复制代码

jetfish1900 发表于 2021-9-5 11:37
非常感谢你的回复。我之前说的while loop就是brute force的solution。我的确没想到可以预先存起来。感觉m ...

感觉没什么问题。