r*****l
发帖数: 41 | 1 A zero-indexed array A consisting of N different integers is given. The
array contains all
integers in the range [0..N - 1]. Sets S[K] for 0 <= K < N are defined as
follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
Sets S[K] are finite for each K.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns the size of the
largest set S[K]
for this array. The function should return 0 if the array is empty.
For example, given array A such that: A[0] = 5, A[1] = 4, A[2] = 0, A[3] =
3, A[4] = 1, A[5] = 6, A[6] = 2
the function should return 4, because set S[2] equals { 0, 5, 6, 2 } and has
four elements.
No other set S[K] has more than four elements.
Assume that:
· N is an integer within the range [0..1,000,000];
· the elements of A are all distinct;
· each element of array A is an integer within the range [0..N-1].
Complexity:
· expected worst-case time complexity is O(N);
· expected worst-case space complexity is O(N), beyond input
storage (not counting
the storage required for input arguments).
Elements of input arrays can be modified.
怎么做? | s*********x
发帖数: 32 | 2 感觉暴力做就能符合要求了。 最长的set是个闭环,所以遍历的时候不用重复了 | r******l
发帖数: 10760 | 3 从S[0]开始数，数过的都从A中标记出来。所以A中的每个元素最多数一次，肯定就是O(
N)了。 | G**O
发帖数: 147 | 4 for (int i = 0; < s.length; i++) {
if (s[i] > 0) {
while (符合条件） {
往后访问
s[i] = -s[i];
}
}
}
每个元素就被访问一次，是O(N), 用负数标记访问，不用额外空间。 | s****3
发帖数: 270 | | o*******r
发帖数: 73 | 6 可否发个完整代码我来学习一下，我觉得你那个while里面还是O(N), 最后下来是N平方。
【在 G**O 的大作中提到】
: for (int i = 0; < s.length; i++) {
: if (s[i] > 0) {
: while (符合条件） {
: 往后访问
: s[i] = -s[i];
: }
: }
: }
: 每个元素就被访问一次，是O(N), 用负数标记访问，不用额外空间。
| C*******A
发帖数: 1980 | 7 线性解法来了 中难度
public static int FindMaxLength2(int[] A)
{
int max = -1, count = 0, next, temp;
for (int i = 0; i < A.Length; i++)
{
if (A[i] == -1) continue;
next = A[i];
count++;
A[i] = -1;
while (next != -1 && A[next] != -1)
{
temp = next;
next = A[next];
A[temp] = -1;
count++;
}
max = max > count ? max : count;
count = 0;
}
return max;
} |
|
