数组嵌套

一个长为 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