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

开启你的职业生涯

完成课程获得认证

开始学习