LeetCode 565——Array Nesting
A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.
Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.
Example 1:
Input: A = [5,4,0,3,1,6,2] Output: 4 Explanation: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2. One of the longest S[K]: S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
Note:
- N is an integer within the range [1, 20,000].
- The elements of A are all distinct.
- Each element of A is an integer within the range [0, N-1].
数组嵌套问题。以零为其实索引长度为N的数组A中所有的整数都在0到N - 1范围内,求集合S的最大长度,S满足如下规则:
S的第一个元素是数组中索引为 i 处对应的 A[i],S中的下一个元素为 A[A[i]] ,下下个元素为 A[A[A[I]]] .... 以此类推,当这个元素已经在S中出现过时,停止添加。满足以上条件的元素组成集合S[i] = {A[i], A[A[i]], A[A[A[i]]], ...}。
同时,下边的注意也很重要,N的范围区间是[1, 20000],并且数组中每个元素都是不同的。
很容易想到的思路是直接暴力循环求解,找到最大的length。暴力不可取,这是必然的。
针对这个思路能够发现一个问题,再循环的过程中,可能会重复求解最佳答案,按照题目给出的例子来讲,从索引为0(值为5)和索引为2(值为0)的位置开始,得到的集合是一样的。
也就是说我们要避免对重复元素的访问,这个时候增加一个对应长度的访问数组visited就可以了。每当访问某索引元素时,检查 i 索引对应的 visited[i] 是否被访问过。
这样的优化已经很不错了,但是进一步思考,这个集合是不是和循环链表类似呢?利用反证法等手段,我们可以证明在此数组中以 A[i] 开始的嵌套循环,一定在A[x] = A[i] 处结束。所以这也就表明这其实就是一个循环链表的遍历过程,数组中多个链表的元素互不相交,这也就意味着,当:数组长度 - 集合长度 < 数组长度 / 2 的时候,就不存在比其更大的集合了,也就可以提前终止循环。
虽然到这里感觉和最开始的暴力求解已经优化了很多,但是考虑一下多出来的空间复杂度O(N),是不是也可以优化?
答案是肯定的,我们可以看到整个程序在上次我们优化过后的过程就是,访问过的元素不会访问第二次了,并且题目没有保持数组元素不改变的要求,因此我们可以将访问过的元素变为一个特定的数字,可以是负数,也可以是Integer.MAX_VALUE。这样空间复杂度就变为了O(1)。
虽然和标准题解的解法一样,但是时间(faster than 98.72%)和内存(less than 28.27%)使用总是不能达到让人满意的程度
AC代码:
class Solution {
public int arrayNesting(int[] nums) {
int numLen = nums.length;
int intMaxValue = Integer.MAX_VALUE;
int result = 0;
for (int i = 0; i < numLen; ++i) {
if (nums[i] != intMaxValue) {
int loopNum = 0;
int preNum = 0;
for (int j = i; nums[j] != intMaxValue; j = preNum, ++loopNum) {
preNum = nums[j];
nums[j] = intMaxValue;
}
if (loopNum > result) {
result = loopNum;
if (numLen - result < numLen / 2) {
return result;
}
}
}
}
return result;
}
}
如有错误,欢迎指摘。也欢迎通过左上角的“向TA提问”按钮问我问题,我将竭力解答你的疑惑。