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

Cho một danh sách số A và một số k. Ta cần 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 lại trước khi vượt quá chỉ mục. Yêu cầu tìm kích thước của tập hợp này, trả về -1 nếu có chu trình.

Ví dụ

Đầu vào: A = [1,2,3,4,5,6,7], k = 1.
Đầu ra: 6 vì A[1]=2, A[2]=3, A[3]=4, A[4]=5, A[5]=6, A[6]=7, tập hợp là {2,3,4,5,6,7}, kích thước = 6.

Thuật toán

1. Khởi tạo tập hợp seen rỗng.
2. Khi k < len(A):
   • Nếu A[k] đã có trong seen, trả về -1 (phát hiện chu trình).
   • Thêm A[k] vào seen.
   • Cập nhật k = A[k].
3. Trả về kích thước của seen.

Mã nguồn Python

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 / Đầu ra

Input: [1,2,3,4,5,6,7], 1
Output: 6