题目描述

索引从 0 开始长度为 N 的数组 A，包含 0 到 N - 1 的所有整数。找到并返回最大的集合 S，S[i] = {A[i], A[A[i]], A[A[A[i]]], … }且遵守以下的规则。

假设选择索引为 i 的元素 A[i] 为 S 的第一个元素，S 的下一个元素应该是 A[A[i]]，之后是 A[A[A[i]]]… 以此类推，不断添加直到 S 出现重复的元素。

样例

输入: A = [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}

注意

• N 是 [1, 20,000] 之间的整数。
• A 中不含有重复的元素。
• A 中的元素大小在 [0, N-1] 之间。

算法

(数论，线性遍历) $O(n)$

1. 简要来看，题目询问的是大小为 N 的置换群中，最大的不可分解的子置换群的大小是多少。由代数结构的知识可以得知，一个置换群是若干个小的最简置换群的结合。
2. 故可以从 0 开始，按照 A[0], A[A[0]] 的顺序寻找一个不可分解的置换群，直到又回到 0 为止。
3. 由代数结构的定理知，遍历过的下标无需重复遍历，故下一次从没有被遍历过的下标开始寻找新的置换群。

时间复杂度

• 每个下标仅被遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int n = nums.size();
        vector<bool> vis(n, false);

        int ans = 0, tmp_length;
        for (int i = 0; i < n; i++)
            if (vis[i] == false) {
                vis[i] = true;
                tmp_length = 1;
                int j = nums[i];
                while (j != i) {
                    vis[j] = true;
                    tmp_length++;
                    j = nums[j];
                }
                ans = max(ans, tmp_length);
            }

        return ans;
    }
};