当前位置：网站首页>565. Array nesting

565. Array nesting

2022-07-19 13:26:00 【51CTO】

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

The first thought is direct violence traversal , Start with each element in the array , See how far you can go ：

from typing import List


class Solution:
    #  violence 
    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.

A operation , Direct timeout .
565. Array nesting _ Array

Think about it , Direct traversal will have many repeated operations .
If an element has already appeared , Then don't look at it anymore .

from typing import List


class Solution:
    #  violence 
    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://yzsam.com/2022/200/202207171810359450.html

当前位置：网站首页>565. Array nesting

565. Array nesting

边栏推荐

猜你喜欢

随机推荐