Chương trình đếm số phần tử có trong một tập hợp các phần tử với lập chỉ mục đệ quy trong Python

Giả sử chúng ta có một danh sách các số được gọi là A và một số khác k, chúng ta phải tạo một tập hợp mới gồm các phần tử có thể có {A [k], A [A [k]], A [A [A [k]]], .. .} dừng trước khi nó nằm ngoài chỉ mục. Chúng tôi phải tìm kích thước của tập hợp này, nếu không thì -1 khi có một chu kỳ.

Vì vậy, nếu đầu vào là A =[1,2,3,4,5,6,7], k =1, thì đầu ra sẽ là 6 là A [1] =2, A [2] =3, A [3] =4, A [4] =5, A [5] =6, A [6] =7, Vậy tập hợp là {2,3,4,5,6,7}, kích thước của tập hợp là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đã thấy:=một tập hợp mới
• while k
• nếu A [k] in được nhìn thấy, thì
  • trả về -1
• chèn A [k] vào đã nhìn thấy
• k:=A [k]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

6