首页 > 试题广场 >

将路径数组变为统计数组

[编程题]将路径数组变为统计数组
  • 热度指数:483 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个路径数组paths,表示一张图。
paths[i]==j代表城市i连向城市j,如果paths[i]==i表示i城市是首都,一张图里只会有一个首都,不会有分图且图中除了首都指向自己之外不会有环;
例如:paths={9,1,4,9,0,4,8,9,0,1} 由这个数组表示的图如下图所示。
城市1是首都所以距离为0;离首都距离为1的城市只有城市9;离首都距离为2的城市有城市0,3,7;离首都距离为3的城市有城市4,8;离首都距离为4的城市有城市2,5,6; 所以,距离为0的城市有1座;距离为1的城市有1座;距离为2的城市有3座;距离为3的城市有2座;距离为4的城市有3座;那么统计数组为numArr={1,1,3,2,3,0,0,0,0,0},numArr[i]==j代表距离为i的城市有j座; 要求实现一个void类型的函数,输入一个路径数组paths,直接在原数组上调整,使之变为numArr数组。 paths={9,1,4,9,0,4,8,9,0,1},函数处理后,paths={1,1,3,2,3,0,0,0,0,0}。 要求:如果paths长度为N,时间复杂度为O(N),额外空间复杂度为O(1);