565. Array nesting: regular simulation questions

Title Description

This is a LeetCode Upper 565. Array nesting , The difficulty is secondary .

Tag : 「 simulation 」

Index from Start length is N Array of A, contain To All integers of . Find the largest set S And return its size , among And abide by the following rules .

Suppose the selection index is i The elements of by S The first element of ,S The next element of should be , And then ... And so on , Keep adding until S Duplicate elements appear .

Example  1:

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

 Output : 4

 explain : 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

 One of the longest  S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Tips ：

• N yes Integer between .
• A There are no duplicate elements in the .
• A The size of the element in Between .

simulation

take And There is a directed edge between , Because all numbers range in , And not repeated , So there is at least one ring , The essence of the problem is to find the maximum length of all rings .

Directly simulate according to the meaning of the title , Deal with each... From front to back , And try to from Start and traverse the ring in which it is located , In order to prevent some rings from being processed repeatedly , For the currently passed Marked as , In this way, each number can be accessed no more than Time , The overall complexity is .

Java Code ：

class Solution {
    public int arrayNesting(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int cur = i, cnt = 0;
            while (nums[cur] != -1) {
                cnt++;
                int c = cur;
                cur = nums[cur];
                nums[c] = -1;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

TypeScript Code ：

function arrayNesting(nums: number[]): number {
    let n = nums.length, ans = 0
    for (let i = 0; i < n; i++) {
        let cur = i, cnt = 0
        while (nums[cur] != -1) {
            cnt++
            const c = cur
            cur = nums[cur]
            nums[c] = -1
        }
        ans = Math.max(ans, cnt)
    }
    return ans
};

• Time complexity ： Each number is accessed a constant number of times , The complexity is
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.565 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases