【Leetcode】565. Array Nesting

Description

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].

Sets S[K] for 0 <= K < N are defined as follows:

S[K] = { A[K], A[A[K]], A[A[A[K]]], … }.

Sets S[K] are finite for each K and should NOT contain duplicates.

Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.

Example

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

1.N is an integer within the range [1, 20,000].
2.The elements of A are all distinct.
3.Each element of array A is an integer within the range [0, N-1].

Solution

First

public int arrayNesting(int[] nums) {
        int index = nums[0];
        int len = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        
        List<Integer> list1 = new ArrayList<>();

        int max = 0;
        for (int i = 0; i < len - max; i++) {
            int thisTurnValue = i;
            int count = 0;
            while (list.contains(nums[thisTurnValue]) && !list1.contains(nums[thisTurnValue])) {
                list1.add(nums[thisTurnValue]);
                count++;
                thisTurnValue = nums[thisTurnValue];
            }
            max = Math.max(max, count);
            if (count > len /2) {
                break;
            }
        }
        return max;
    }

Result

TLE

Analyse

pass了853 / 856test cases，还是限制了，我认为是这次判断没办法给后面的判断给予支援，其实如果list如果能保存下来，判断下次进入了同样的list，那就不用判断了。

Optimization

public int arrayNesting(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int size = 0;
            for (int k = i; nums[k] >= 0; size++) {
                int numk = nums[k];
                nums[k] = -1;
                k = numk;
            }
            max = Math.max(max, size);
        }
        return max;
    }

Analyse

这种情况下其实就利用了这个数组本身的特性，因为他可以根据index往下循环，那肯定是index不会小于0，每次走过之后将该index所在的值对应为-1，这样就会影响整个数组，那么外面的循环走到这个一样的判断，其实就不用走了。