565. Array Nesting - Mediaum
문제
You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].
You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], … } subjected to the following rule:
- The first element in s[k] starts with the selection of the element nums[k] of index = k.
- The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.
- We stop adding right before a duplicate element occurs in s[k].
Return the longest length of a set s[k].
제한사항
- 1 <= nums.length <= 105
- 0 <= nums[i] < nums.length
- All the values of nums are unique.
입출력 예
1
2
3
4
5
6
7
8
Example 1:
Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
1
2
3
4
Example 2:
Input: nums = [0,1,2]
Output: 1
풀이
- Array, DFS
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
26
27
28
29
30
31
32
33
34
type Item struct {
Depth int
NextIndex int
}
func arrayNesting(nums []int) int {
// 불필요한 검색을 피하기 위해
// 이미 확인한 index를 표시
depth := 0
cheker := make([]bool, len(nums))
for i, _ := range(nums) {
var s []Item
s = append(s, Item{1, nums[i]})
cheker[i] = true
for len(s) != 0 {
item := s[len(s) - 1]
s = s[:len(s) - 1]
if (cheker[item.NextIndex]) {
if (depth < item.Depth) {
depth = item.Depth
}
} else {
s = append(s, Item{item.Depth + 1, nums[item.NextIndex]})
cheker[item.NextIndex] = true
}
}
}
return depth
}