LeetCode 565. Array Nesting

问题描述

给定一个长度为 N 的数组 A，它包含不同的整数，且取值范围为 0 ~ N-1。找出长度最长的集合 S，其中S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }，满足如下规则。

假设 S 的第一个元素是 A[i]，下一个元素是 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[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

注意：

N 是一个整数，范围在 [1, 20000] 之间。
A 中的元素都不相同。
A 中的每个元素范围在 [0, N-1] 之间。

想看英文原文的戳这里。

解题思路

简单解读一下题意：

首先从数组中任意取一个元素 a1，加入到集合 S。
然后将 a1 作为数组的下标，得到一个数 a2，加入到集合 S。
再将 a2 作为数组的下标，得到一个数 a3，加入到集合 S。
...
如此循环往复，直到得到的数跟集合中的数有重复时，则停止。

最常规解法

最直接最容易想到的方式，应该就是分别计算从 i （0 <= i < N-1）开始的数字链长度，然后比较得出最大值。

代码也比较简单，如下：

var arrayNesting = function (nums) {
  let i = 0;
  let maxLen = 0;

  while (i < nums.length) {
    let next = nums[i];
    let count = 0;

    do {
      count += 1;
      next = nums[next];
    } while (next !== nums[i])

    maxLen = Math.max(maxLen, count);

    i += 1;
  }

  return maxLen;
};

优化解法

当出现重复的数字时，肯定是构成了环。环的特性是，无论从环中的哪个数字出发，环的长度始终是一样的。因此，当遇到同样的环时，则可跳过计算。该优化解法也就是基于此。

举个栗子。比如，A = [5,4,0,3,1,6,2]，其中一个环为 5-6-2-0-5。那么从 5/6/2/0 开始的数，组成集合的长度都是 4。

但如何判断进入了以前计算过的环呢？方式也比较简单，只需将访问过的元素进行标记即可。当遇到的元素被标记过，则不用处理。

而标记也有两种实现方式：

使用额外数组记录。
在原有数组上记录。

方式 1 的代码如下：

var arrayNesting = function (nums) {
  let maxLen = 0;

  // 记录是否访问过
  let visited = [];

  // 初始化
  let i = 0;
  while (i < nums.length) {
    visited.push(false);
    i += 1
  }

  i = 0
  while (i < nums.length) {
    let next = nums[i];
    let count = 0;

    if (!visited[i]) {
      do {
        count += 1;
        next = nums[next];
      } while (next !== nums[i])

      visited[i] = true;
      maxLen = Math.max(maxLen, count);
    }

    i += 1;
  }

  return maxLen;
};

方式 2，在原有数组上标记，即将访问过的元素置为 -1。当遇到 -1，则不用计算。

java 代码如下：

public class Solution {
    public int arrayNesting(int[] a) {
        int maxsize = 0;
        for (int i = 0; i < a.length; i++) {
            int size = 0;
            for (int k = i; a[k] >= 0; size++) {
                int ak = a[k];
                a[k] = -1; // mark a[k] as visited;
                k = ak;
            }
            maxsize = Integer.max(maxsize, size);
        }

        return maxsize;
    }
}