leetcode 565 （高级编程技术week9-2）

- 日理万妓 2022-05-24 23:17 145阅读 0赞

# leetcode 565 （高级编程技术week9-2） #

题目链接可见[https://leetcode.com/problems/array-nesting/description/][https_leetcode.com_problems_array-nesting_description]

## 题目 ##

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S\[i\] = \{A\[i\], A\[A\[i\]\], A\[A\[A\[i\]\]\], … \} subjected to the rule below.

Suppose the first element in S starts with the selection of element A\[i\] of index = i, the next element in S should be A\[A\[i\]\], and then A\[A\[A\[i\]\]\]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:
    Input: A = [5,4,0,3,1,6,2]
    Output: 4
    
    Explanation: 
    A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
    
    One of the longest S[K]:
    S[0] = {
       A[0], A[5], A[6], A[2]} = {
       5, 6, 2, 0}
    Note:
    N is an integer within the range [1, 20,000].
    The elements of A are all distinct.
    Each element of A is an integer within the range [0, N-1].

## 题目分析 ##

这里题目要求的是：返回一个最大集合的长度。其中这个集合需要满足的条件如题目所示。

仔细分析这个集合的特点，若一个数字在这样的一个集合中，这个集合内的元素必然连成一个环。

如题目的示例，可构成这样的一个环

\{% asset\_img 2018-05-04-06-30-41.png this is an image %\}

可知数组中的所有元素最后必定能够划分为独立的M个环，现在的问题就是求最大的环的长度了。

毫无疑问，我需要遍历每一个元素。

1.  若这个元素所在的环我已经算过了，那我就直接返回这个环的长度
2.  若这个元素所在的环我没有算过，那我就算一算

现在的问题是，对一个元素，我如何知道它所在的环被算过？知道被算过我又如何找到对应的环的长度？

这就需要我先清楚使用什么数据结构来存储我的计算结果。

当一个元素我没有计算过的时候，我通过一个集合存放当前环的元素，循环将下一个元素放入集合中，直到下一个元素已经在集合中。此时我们便计算得出了一个环的长度，并且这个环里的所有元素我以集合的方式存储进来。

我使用一个额外的数组存放每一个数组对应的环的长度，在计算一个环的长度后，我可以将环内的所有元素在数组中对应的位置的值置为环的长度，此后我便可以通过直接访问该数组的方式来得到环的长度，若为0，表示没计算过，那就去算。

## 代码展示 ##

class Solution:
        def arrayNesting(self, nums):
            """ :type nums: List[int] :rtype: int """
            self.nums = nums
            self.lens = [0 for _ in range(len(nums))]
            max_len = 0
            for i in range(len(nums)):
                cur_len = self.get_len(self.nums[i])
                if max_len < cur_len:
                    max_len = cur_len
            return max_len
        def get_len(self, num):
            if self.lens[num]:
                return self.lens[num]
            loop = set()
            loop.add(num)
            cur_num = num
            while (self.nums[cur_num] not in loop):
                loop.add(self.nums[cur_num])
                cur_num = self.nums[cur_num]
            for i in loop:
                self.lens[i] = len(loop)
            # print(loop)
            return len(loop)

\{% asset\_img 2018-05-04-06-53-16.png this is an image %\}

这个方法似乎还不够快,其实想了一下，没有必要用集合。

## 优化 ##

这里放一个大神的代码参考，简洁，优雅。

class Solution(object):
        def arrayNesting(self, nums):
            """ :type nums: List[int] :rtype: int """
            ans, step, n = 0, 0, len(nums)
            seen = [False] * n
            for i in range(n):
                while not seen[i]:
                    seen[i] = True
                    i, step = nums[i], step + 1
                ans = max(ans, step)
                step = 0
            return ans

这个代码beat了84.44%的python3 solutions。

[https_leetcode.com_problems_array-nesting_description]: https://leetcode.com/problems/array-nesting/description/