565. Array Nesting

leetcode.com/problems/array-nesting/

- Worng answer

'''
길이 N인 리스트 A [0, 1, 2, .. N-1]
다음을 만족하는 가장 긴 길이의 set S를 리턴
S[i] = {A[i], A[A[i]], A[A[A[i]]]}

'''
class Solution(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = []
        mySet = set()
        index = 0

        while nums[index] not in mySet:
            ans.append(nums[index])
            mySet.add(nums[index])
            index = nums[index]  # prepare next index
        return len(ans)

        

A[0] = 0 인경우 다른 Set을 고려하지 못하게 된다.

- Time Limit Exceeded

class Solution(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxNum = -1
        for index in range(0, len(nums)):
            ans = []
            mySet = set()
            while nums[index] not in mySet:
                ans.append(nums[index])
                mySet.add(nums[index])
                index = nums[index]  # prepare next index
            if len(ans) > maxNum:
                maxNum = len(ans)
        return maxNum

 

모든 경우 index를 돌았기 때문에 시간 초과

- Success Answer

class Solution(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numsSet = set(nums)
        maxNum = -1
        index = 0

        while len(numsSet) > maxNum:
            mySet = set()
            while nums[index] not in mySet:
                mySet.add(nums[index])
                index = nums[index]  # prepare next index
            numsSet -= mySet
            index += 1
            if len(mySet) > maxNum:
                maxNum = len(mySet)
        return maxNum

순환되는 set이 나오면 list에서 제외하면 반복을 줄일 수 있다.

- Best Answer

def arrayNesting(self, nums: List[int]) -> int:
        mx = 0
        for i in range(len(nums)):
            if nums[i] == -1: continue # continue if we already met it
            length = 0
            while nums[i] != -1: # stop when we meet the same number twice
                nums[i], i = -1, nums[i]
                length += 1
            if length > mx: mx = length
        return mx