Tìm và trả về độ dài tập hợp lớn nhất bằng JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số, arr, làm đối số đầu tiên và duy nhất.

Mảng arr độ dài N chứa tất cả số nguyên từ 0 đến N-1. Hàm phải tìm và trả về độ dài lớn nhất của tập hợp S, với S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } tuân theo quy tắc:

Giả sử phần tử đầu tiên trong S bắt đầu bằng việc chọn phần tử A[i] chỉ số = i, phần tử tiếp theo trong S nên là A[A[i]], rồi A[A[A[i]]]... Theo cách đó, dừng lại ngay trước khi phần tử trùng lặp xuất hiện trong S.

Ví dụ, nếu đầu vào là:

const arr = [5, 4, 0, 3, 1, 6, 2];

Thì đầu ra nên là:

const output = 4;

Giải thích kết quả

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

Một trong các S[K] dài nhất:

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Ví dụ

Dưới đây là mã:

const arr = [5, 4, 0, 3, 1, 6, 2]; 
const arrayNesting = (arr = []) => { 
  const visited = {} 
  const aux = (index) => { 
    if (visited[index]) { 
      return 0 
    } 
    visited[index] = true 
    return aux(arr[index], visited) + 1 
  } 
  let max = 0 
  arr.forEach((n, index) => { 
    if (!visited[index]) { 
      max = Math.max(max, aux(index)) 
    } 
  }) 
  return max 
} 
console.log(arrayNesting(arr));

Kết quả

Kết quả console:

4