[LeetCode] 565. Array Nesting

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:

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:

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

数组嵌套。

题意很简单，给一个长度为N的数组，包含的数字从0到N - 1，请找出数组中最长的环的长度。

思路也不难想，无非就是找环的长度。讨论区有一个评论写的很好，这里有一个细节需要想清楚，因为包含的数字是从0到N - 1，而且因为是数组的关系，每个数字的入度只有可能是1。所以如果开始出现环了，这个环上所有的数字是不可能再跟别的环有关系了，而且环的长度会在发现第一个重复数字的时候就停止增长了。

至于怎么找环，可以将遍历过的数字改成-1，这样下次再次遍历的时候如果当前位置上的数字已经是-1了则说明找到环了。或者可以另外创建一个visited数组记录，以免污染input数组。

直接改input数组

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int arrayNesting(int[] nums) {
 3         int res = 0;
 4         for (int i = 0; i < nums.length; i++) {
 5             // curIndex是当前的index
 6             int curIndex = i;
 7             int count = 0;
 8             while (nums[curIndex] != -1) {
 9                 count++;
10                 int temp = curIndex;
11                 curIndex = nums[curIndex];
12                 nums[temp] = -1;
13             }
14             res = Math.max(res, count);
15         }
16         return res;
17     }
18 }

创建额外数组记录是否访问过

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int arrayNesting(int[] nums) {
 3         int maxLen = 0;
 4         boolean[] visited = new boolean[nums.length];
 5         for (int n : nums) {
 6             int curLen = 0;
 7             while (!visited[n]) {
 8                 curLen++;
 9                 visited[n] = true;
10                 n = nums[n];
11             }
12             maxLen = Math.max(maxLen, curLen);
13         }
14         return maxLen;
15     }
16 }

LeetCode 题目总结