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}

注意:

  1. N 是一个整数,范围在 [1, 20000] 之间。
  2. A 中的元素都不相同。
  3. 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. 使用额外数组记录。
  2. 在原有数组上记录。

方式 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;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。