LeetCode 565. Array Nesting

 关注
发布于: 2020 年 07 月 19 日
问题描述﻿
给定一个长度为 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;
    }
}
﻿
发布于: 2020 年 07 月 19 日阅读数: 28
原文链接:【http://xie.infoq.cn/article/ad916278bf87b1727082779e8】。文章转载请联系作者。
liu_liu

 关注
不要相信自己的记忆力 2017.11.13 加入
还未添加个人简介
发布
暂无评论