leetcode 565. Array Nesting

Posted on | | 阅读数
Words count in article: 169 | Reading time ≈ 1

Question

Solution

分析，我们可以将nums中的数分成几组。如果某组的第一个数出现两次，则在第二次出现的时候就需要退出循环，并且已经达到最大的step。将第一个循环的数从nums剔除或者不考虑，继续对下一个循环进行计算step。但是剔除会很消耗时间，因为需要复制和遍历来找到需要剔除的数值。所以考虑其他方法。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        max_, step, n = 0, 0, len(nums)
        seen = [False] * n
        for i in range(n):
            while not seen[i]:
                seen[i] = True
                i = nums[i]
                step += 1
            max_ = max(max_, step)
            step = 0
        return max_