数组嵌套 array-nesting

一个长为 N 且下标从 0 开始的数组 A 包含 从 0 到 N - 1 的所有整数。找到并返回集合 S 的最大长度，其中S [i] = {A [i]，A [A [i]]，A [A [A [i]]]，...}受到以下规则的约束。

假设 S 中的第一个元素以选择 index = i的元素A [i]开始，S中的下一个元素应该是A [A [i]]，然后是A [A [A [i]]] ... 通过这个类比，我们在S中出现重复元素之前就停止添加。

array-nesting

样例1

输入: [5,4,0,3,1,6,2]
输出: 4
解释: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

其中一个最长的S [K]：
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

样例2

输入: [0,1,2]
输出: 1

题意：关键是弄懂 S [i] = {A [i]，A [A [i]]，A [A [A [i]]]，...}
                

思路1、使用递归会超时 使用 set 存储 s[i] 中的元素，出现重复的递归结束



思路2、遍历数组 使用 set 存在 s[i]中的元素，当 set 出现重复的时候跳过， 定义一个中间变量 temp white循环set 不包含 temp 实现如下

public class Solution {
 /**
     * @param nums: an array
     * @return: the longest length of set S
     */
    public int arrayNesting(int[] nums) {
        // Write your code here
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> set = new HashSet<>();
            helper(nums, i, set);
            result = Math.max(result, set.size());
        }

        return result;

    }

    private void helper(int[] nums, int i, Set<Integer> set) {
        if (set.contains(nums[i])) {
            return;
        }
        set.add(nums[i]);
        helper(nums, nums[i], set);
    }

public class Solution {
     /**
     * @param nums: an array
     * @return: the longest length of set S
     */
    public int arrayNesting(int[] nums) {
        int result = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(i)) {
                continue;
            }
            int count = 0;
            int temp =i;
            while (!set.contains(temp)) {
                set.add(temp);
                count++;
                temp = nums[temp];

            }
            result = Math.max(result, count);
        }

        return result;
    }
    }
}

源码地址 https://github.com/xingfu0809/Java-LintCode