สมมติว่ามีรายการตัวเลขชื่อ A และอีกตัวเลขหนึ่งคือ k เราต้องสร้างชุดใหม่ขององค์ประกอบที่เป็นไปได้ {A[k], A[A[k]], A[A[A[k]]], ...} จนกว่าจะเกินดัชนี เราต้องหาขนาดของชุดนี้ มิฉะนั้นคืนค่า -1 เมื่อมีวงจร
เช่น ถ้าอินพุตเป็น A = [1,2,3,4,5,6,7], k = 1 ผลลัพธ์จะเป็น 6 เพราะ 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
ขั้นตอนการแก้ปัญหา
- seen := ชุดใหม่
- while k < ขนาดของ A ทำ
- ถ้า A[k] อยู่ใน seen แล้ว คืนค่า -1
- นำ A[k] ใส่เข้า seen
- k := A[k]
- คืนค่าขนาดของ seen
ตัวอย่างโค้ด
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
เอาต์พุต
6
