0565-数组嵌套

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

索引从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出现重复的元素。

示例 1:

**输入:** 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}

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] < nums.length
  • A中不含有重复的元素。

方法一：图

遍历数组，从 i 向 nums}[i] 连边，我们可以得到一张有向图。

由于题目保证 nums 中不含有重复的元素，因此有向图中每个点的出度和入度均为 1。

在这种情况下，有向图必然由一个或多个环组成。我们可以遍历 nums，找到节点个数最大的环。

代码实现时需要用一个 vis 数组来标记访问过的节点。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        vis = [False] * n
        for i in range(n):
            cnt = 0
            while not vis[i]:
                vis[i] = True
                i = nums[i]
                cnt += 1
            ans = max(ans, cnt)
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int arrayNesting(vector<int> &nums) {
        int ans = 0, n = nums.size();
        vector<int> vis(n);
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            while (!vis[i]) {
                vis[i] = true;
                i = nums[i];
                ++cnt;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int arrayNesting(int[] nums) {
        int ans = 0, n = nums.length;
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            while (!vis[i]) {
                vis[i] = true;
                i = nums[i];
                ++cnt;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int ArrayNesting(int[] nums) {
        int ans = 0, n = nums.Length;
        bool[] vis = new bool[n];
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            while (!vis[i]) {
                vis[i] = true;
                i = nums[i];
                ++cnt;
            }
            ans = Math.Max(ans, cnt);
        }
        return ans;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func arrayNesting(nums []int) (ans int) {
    vis := make([]bool, len(nums))
    for i := range vis {
        cnt := 0
        for !vis[i] {
            vis[i] = true
            i = nums[i]
            cnt++
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int arrayNesting(int* nums, int numsSize){
    int ans = 0;
    bool *vis = (bool *)malloc(sizeof(bool) * numsSize);
    memset(vis, 0, sizeof(bool) * numsSize);
    for (int i = 0; i < numsSize; ++i) {
        int cnt = 0;
        while (!vis[i]) {
            vis[i] = true;
            i = nums[i];
            ++cnt;
        }
        ans = MAX(ans, cnt);
    }
    free(vis);
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arrayNesting = function(nums) {
    let ans = 0, n = nums.length;
    const vis = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        let cnt = 0;
        while (!vis[i]) {
            vis[i] = true;
            i = nums[i];
            ++cnt;
        }
        ans = Math.max(ans, cnt);
    }
    return ans;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(n)。

方法二：原地标记

利用「nums 中的元素大小在 [0, n-1] 之间」这一条件，我们可以省略 vis 数组，改为标记 nums}[i] = n，来实现和 vis 数组同样的功能。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            cnt = 0
            while nums[i] < n:
                num = nums[i]
                nums[i] = n
                i = num
                cnt += 1
            ans = max(ans, cnt)
        return ans
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int arrayNesting(vector<int> &nums) {
        int ans = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            while (nums[i] < n) {
                int num = nums[i];
                nums[i] = n;
                i = num;
                ++cnt;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int arrayNesting(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            while (nums[i] < n) {
                int num = nums[i];
                nums[i] = n;
                i = num;
                ++cnt;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int ArrayNesting(int[] nums) {
        int ans = 0, n = nums.Length;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            while (nums[i] < n) {
                int num = nums[i];
                nums[i] = n;
                i = num;
                ++cnt;
            }
            ans = Math.Max(ans, cnt);
        }
        return ans;
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func arrayNesting(nums []int) (ans int) {
    n := len(nums)
    for i := range nums {
        cnt := 0
        for nums[i] < n {
            i, nums[i] = nums[i], n
            cnt++
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int arrayNesting(int* nums, int numsSize){
    int ans = 0;
    for (int i = 0; i < numsSize; ++i) {
        int cnt = 0;
        while (nums[i] < numsSize) {
            int num = nums[i];
            nums[i] = numsSize;
            i = num;
            ++cnt;
        }
        ans = MAX(ans, cnt);
    }
    return ans;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arrayNesting = function(nums) {
    let ans = 0, n = nums.length;
    for (let i = 0; i < n; ++i) {
        let cnt = 0;
        while (nums[i] < n) {
            const num = nums[i];
            nums[i] = n;
            i = num;
            ++cnt;
        }
        ans = Math.max(ans, cnt);
    }
    return ans;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(1)，我们只需要常数的空间保存若干变量。

 Comments
On this page
0565-数组嵌套