Description:
https://leetcode.com/problems/array-nesting/description/
Algorithm:
Actually we are separating the array into several groups by determining S[k]. The numbers inside of S[k] will form a cycle.
For example:
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}
S[5] = {A[5], A[6], A[2], A[0]} = {6, 2, 0, 5}
S[6] = {A[6], A[2], A[0], A[5]} = {2, 0, 5, 6}
S[2] = {A[2], A[0], A[5], A[6]} = {0, 5, 6, 2}
S[1] = {A[1], A[4]} = {4,1}
S[4] = {A[4], A[1]} = {1,4}
S[3] = {A[3]} = {3}
So just mark the used number in the finding process. If meets used number -> stop.
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public: int arrayNesting(vector<int>& nums) { int n = nums.size(); int currentIdx = 0; int maxLength = 0; int currentLength = 0; int IdxTemp = 0; for (int i = 0; i < n; i++) { currentIdx = i; currentLength = 0; while(nums[currentIdx] != -1) { IdxTemp = currentIdx; currentIdx = nums[IdxTemp]; nums[IdxTemp] = -1; currentLength++; } maxLength = currentLength > maxLength? currentLength : maxLength; } return maxLength; } }; |
Timing & Space:
fastest
O(n) & O(1)