欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 565. Array Nesting

程序员文章站 2022-06-01 21:34:22
...
"""
max = Max(current_max, max)
Use a flag array to mark if current node has been visited before.
If it is visited, then we can skip it. 
Complexity is O(n) as we only go through the array once.
"""

class Solution:
    """
    @param nums: an array
    @return: the longest length of set S
    """
    def arrayNesting(self, nums):
        # Write your code here
        arr_len = len(nums)
        max_length = 0
        flag = [False] * arr_len
        
        for i in range(arr_len):
            if flag[i] is False:
                max_length = max(max_length, self.currentMax(i, nums, flag, arr_len))
                
        return max_length
    
    def currentMax(self, i, nums, flag, arr_len):
        currentmax = 0
        while True:
            if i<arr_len and flag[i] is False:
                flag[i] = True
                currentmax += 1
                i = nums[i]
            else:
                break
                
        return currentmax

 

相关标签: Apple