565. Array Nesting

leetcode medium

#array#csharp#hash-table#leetcode#math#medium

Task

Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].

Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:

Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.

Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.

Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.

Верните длину самого длинного множества s[k].

Пример:

Input: nums = [5,4,0,3,1,6,2]

Output: 4

Explanation:

nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.

One of the longest sets s[k]:

s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

C# solution

matched/original

public class Solution {
    public int ArrayNesting(int[] nums) {
        bool[] visited = new bool[nums.Length];
        int maxLength = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.Max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ArrayNesting(vector<int>& nums) {
        bool[] visited = new bool[nums.size()];
        int maxLength = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

Java solution

matched/original

public class Solution {
    public int arrayNesting(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        int maxLength = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

JavaScript solution

matched/original

class Solution {
    arrayNesting(nums) {
        const visited = new Array(nums.length).fill(false);
        let maxLength = 0;
        
        for (let i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                let start = i;
                let count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}

Python solution

matched/original

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        visited = [False] * len(nums)
        max_length = 0
        
        for i in range(len(nums)):
            if not visited[i]:
                start = i
                count = 0
                while not visited[start]:
                    visited[start] = True
                    start = nums[start]
                    count += 1
                max_length = max(max_length, count)
        
        return max_length

Go solution

matched/original

func arrayNesting(nums []int) int {
    visited := make([]bool, len(nums))
    maxLength := 0
    
    for i := 0; i < len(nums); i++ {
        if !visited[i] {
            start := i
            count := 0
            for !visited[start] {
                visited[start] = true
                start = nums[start]
                count++
            }
            if count > maxLength {
                maxLength = count
            }
        }
    }
    
    return maxLength
}

Explanation

Algorithm

Создайте массив для отслеживания посещенных элементов.

Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.

Обновите максимальную длину найденного множества.

😎