模拟
直观思考，一次遍历 n u m s nums n u m s ，对遍历到的每个位置 i i i ，进行嵌套遍历，标记已遍历的数，在接下来的遍历，就不考虑已标记过的数了。
提示 : 嵌套数组是个环，对 i i i 嵌套遍历，一定会回到 i i i 。
代码展示
标记数组
class Solution {
public:
int arrayNesting(vector<int>& nums) {
bool visit[nums.size()];
memset(visit,false,sizeof visit);
int ans = 0;
for(int i = 0;i<nums.size();i++){
int len = 0;
while(!visit[i]){
visit[i] = true;
i=nums[i];
len++;
}
ans = max(ans,len);
}
return ans;
}
};
原地修改
class Solution {
public:
int arrayNesting(vector<int>& nums) {
int ans = 0;
for(int i = 0;i<nums.size();i++){
int len = 0;
while(-1!=nums[i]){
int t = i;
i=nums[i];
nums[t] = -1;
len++;
}
ans = max(ans,len);
}
return ans;
}
};
博主致语
理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。
AC
; 复杂度分析
标记数组
- 时间复杂度:O ( n ) O(n)O (n )，n n n 是n u m s nums n u m s 的长度，一次遍历n u m s nums n u m s 的时间复杂度O ( n ) O(n)O (n ) 。
- 空间复杂度:O ( n ) O(n)O (n )，v i s i t visit v i s i t 数组的空间复杂度是O ( n ) O(n)O (n ) 。
原地修改
- 时间复杂度:O ( n ) O(n)O (n )，n n n 是n u m s nums n u m s 的长度，一次遍历n u m s nums n u m s 的时间复杂度O ( n ) O(n)O (n ) 。
- 空间复杂度:O ( 1 ) O(1)O (1 )，除若干变量使用的常量级空间，没有使用额外的线性空间。
Original: https://blog.csdn.net/Innocence02/article/details/127822187
Author: 清墨韵染
Title: 力扣(LeetCode)565. 数组嵌套(C++)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/658723/
转载文章受原作者版权保护。转载请注明原作者出处！