力扣(LeetCode)565. 数组嵌套(C++)

模拟

直观思考，一次遍历 $nums$ ，对遍历到的每个位置 $i$ ，进行嵌套遍历，标记已遍历的数，在接下来的遍历，就不考虑已标记过的数了。
提示 : 嵌套数组是个环，对 $i$ 嵌套遍历，一定会回到 $i$ 。

代码展示

标记数组

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        bool visit[nums.size()];
        memset(visit,false,sizeof visit);
        int ans = 0;
        for(int i = 0;i<nums.size();i++){
            int len = 0;
            while(!visit[i]){
                visit[i] = true;
                i=nums[i];
                len++;
            }
            ans = max(ans,len);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

原地修改

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int ans = 0;
        for(int i = 0;i<nums.size();i++){
            int len = 0;
            while(-1!=nums[i]){
                int t = i;
                i=nums[i];
                nums[t] = -1;
                len++;
            }
            ans = max(ans,len);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

标记数组

1. 时间复杂度: $O(n)$， $n$ 是 $nums$ 的长度，一次遍历 $nums$ 的时间复杂度 $O(n)$ 。
2. 空间复杂度: $O(n)$，$visit$ 数组的空间复杂度是 $O(n)$ 。

原地修改

1. 时间复杂度: $O(n)$， $n$ 是 $nums$ 的长度，一次遍历 $nums$ 的时间复杂度 $O(n)$ 。
2. 空间复杂度: $O(1)$，除若干变量使用的常量级空间，没有使用额外的线性空间。