当前位置：网站首页>565.数组嵌套

565.数组嵌套

2022-07-17 18:13:00 【51CTO】

https://leetcode.cn/problems/array-nesting/

首先想到的是直接暴力遍历,以数组中每一个元素为起点，看最远能走多远：

from typing import List


class Solution:
    # 暴力
    def arrayNesting(self, nums: List[int]) -> int:
        result = 0
        for x in nums:
            next_n = x
            s = set()
            while next_n not in s:
                s.add(next_n)
                next_n = nums[next_n]


            if len(s) > result:
                result = len(s)
        
        return result

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

一顿操作，直接超时。
565.数组嵌套_数组

思考一下，直接遍历会有很多重复的操作。
如果某个元素已经出现过了，那么就不用再看它了。

from typing import List


class Solution:
    # 暴力
    def arrayNesting(self, nums: List[int]) -> int:
        has_appeared = set()
        result = 0
        for x in nums:
            if x in has_appeared:
                continue
            next_n = x
            s = set()
          
            while next_n not in s:
                has_appeared.add(next_n)
                s.add(next_n)
                next_n = nums[next_n]
            if len(s) > result:
                result = len(s)
        
        return result

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/pigeon/5479976

当前位置：网站首页>565.数组嵌套

565.数组嵌套

边栏推荐

猜你喜欢

随机推荐