Medium

题目描述

给定一个长度为 n 的整数数组 nums，其中 nums 是范围 [0, n - 1] 内数字的一个排列。

你需要构建一个集合 s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], … }，遵循以下规则：

  • s[k] 中的第一个元素从选择索引为 k 的元素 nums[k] 开始
  • s[k] 中的下一个元素应该是 nums[nums[k]]，然后是 nums[nums[nums[k]]]，以此类推
  • 在 s[k] 中出现重复元素之前停止添加

返回最长的集合 s[k] 的长度。

示例 1：

输入：nums = [5,4,0,3,1,6,2]
输出：4
解释：
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2
最长的集合 s[k] 之一：
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

示例 2：

输入：nums = [0,1,2]
输出：1

约束条件：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < nums.length
  • nums 的所有值都是唯一的

解题思路

这是一个寻找环的问题。由于数组是 [0, n-1] 的排列，从任意位置开始按照规则跳转，最终一定会形成环。

解法一：暴力枚举（超时） 对每个起点都计算一遍环的长度，时间复杂度 O(n²)。

解法二：访问标记优化（推荐） 由于每个数字都是唯一的，从任意起点开始的路径最终会形成一个环，且每个数字只会属于一个环。我们可以用访问标记来避免重复计算：

  • 对于每个未访问的位置，开始遍历环并标记所有访问过的位置
  • 计算当前环的长度，更新最大值
  • 已访问的位置不需要再作为起点计算

解法三：原地标记 利用数组元素的符号来标记访问状态，避免额外的空间开销。遍历过的位置将其值标记为负数。

时间复杂度：O(n) - 每个元素最多被访问一次 空间复杂度：O(1) - 原地标记不需要额外空间

代码实现

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) {
                int len = 0;
                int j = i;
                
                while (nums[j] >= 0) {
                    int next = nums[j];
                    nums[j] = -1; // 标记为已访问
                    j = next;
                    len++;
                }
                
                maxLen = max(maxLen, len);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        
        for i in range(n):
            if nums[i] >= 0:
                length = 0
                j = i
                
                while nums[j] >= 0:
                    next_j = nums[j]
                    nums[j] = -1  # 标记为已访问
                    j = next_j
                    length += 1
                
                max_len = max(max_len, length)
        
        return max_len

public class Solution {
    public int ArrayNesting(int[] nums) {
        int n = nums.Length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) {
                int len = 0;
                int j = i;
                
                while (nums[j] >= 0) {
                    int next = nums[j];
                    nums[j] = -1; // 标记为已访问
                    j = next;
                    len++;
                }
                
                maxLen = Math.Max(maxLen, len);
            }
        }
        
        return maxLen;
    }
}

var arrayNesting = function(nums) {
    const n = nums.length;
    let maxLen = 0;
    
    for (let i = 0; i < n; i++) {
        if (nums[i] >= 0) {
            let len = 0;
            let j = i;
            
            while (nums[j] >= 0) {
                const next = nums[j];
                nums[j] = -1; // 标记为已访问
                j = next;
                len++;
            }
            
            maxLen = Math.max(maxLen, len);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
原地标记O(n)O(1)
访问数组标记O(n)O(n)

说明：

  • 时间复杂度：O(n)，每个元素最多被访问一次
  • 空间复杂度：O(1)，原地修改数组进行标记

相关题目