Python에서 재귀 인덱싱을 사용하여 요소 집합에 있는 요소 수를 계산하는 프로그램

<시간/>

A라는 숫자 목록과 또 다른 숫자 k가 있다고 가정하고 가능한 요소 {A[k], A[A[k]], A[A[A[k]]], ..의 새 집합을 만들어야 합니다. . } 인덱스를 벗어나기 전에 중지합니다. 우리는 이 세트의 크기를 찾아야 하고, 그렇지 않으면 사이클이 있을 때 -1입니다.

따라서 입력이 A =[1,2,3,4,5,6,7], k =1과 같으면 출력은 A[1] =2, A[2] =3, A[3] =4, A[4] =5, A[5] =6, A[6] =7, 따라서 집합은 {2,3,4,5,6,7}이고 집합의 크기는 6.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

본 :=새로운 세트
k
만약 A[k]가 보인다면,
- 반환 -1
본에 A[k] 삽입
k :=A[k]

본 것의 반환 크기

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution:
   def solve(self, A, k):
      seen = set()
      while k < len(A):
         if A[k] in seen:
            return -1
         seen.add(A[k])
         k = A[k]
      return len(seen)
ob = Solution()
print(ob.solve([1,2,3,4,5,6,7], 1))

입력

[1,2,3,4,5,6,7], 1