Python遞迴索引計數集合元素個數的程式

假設我們有一個名為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 := 一個新的集合
• 當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

Arnab Chakraborty

更新於：2020年10月7日

瀏覽量：181

開啟你的職業生涯

完成課程獲得認證

開始學習