10/09狗家新鲜面经

楼主最后结果如何

请问楼主这题的时间复杂度，找 children 的操作需要 scan 整个 array？所以是 O(N)? 那整体是 O(N^2) 么？

pmpkhugh 发表于 2018-10-23 04:23
请问楼主这题的时间复杂度，找 children 的操作需要 scan 整个 array？所以是 O(N)? 那整体是 O(N^2) 么？

是的，每步更新都要重新扫array。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

sherry0419 发表于 2018-10-23 06:39
是的，每步更新都要重新扫array。

这样复杂度有点高了，其实可以先根据给定array，建立出父节点与所有子节点的对应关系出来，这样可以把时间复杂度压缩到O(N)的

請問為甚麼
      A
     /  \
   B    C
  /     / \
D    E   F
可以表示成
[[0,A], [0, B], [1,D], [0,C], [3,E], [3,F]]
數字部份完全不了解

lf963 发表于 2018-10-23 11:37
請問為甚麼
      A
     /  \

同问
紫薯 紫薯 紫薯紫薯