LeetCode 565. Array Nesting

用户头像
liu_liu
关注
发布于: 2020 年 07 月 19 日
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;
}
}



发布于: 2020 年 07 月 19 日 阅读数: 15
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 565. Array Nesting