欢迎光临散文网 会员登陆 & 注册

997. 找到小镇的法官

2023-01-05 22:15 作者:目标力扣Knight  | 我要投稿

题意简述

  • 所有人信任法官,法官不信任所有人;

  • 0 <= trust.length <= 10^4

  • trust[i].length == 2

方法一:集合 + 哈希

分别用两个数组peo 和  jud 存储trust 数组每个人员编号以及他们信任的法官编号,统计每个法官编号出现的次数。遍历jud数组,如果某一个编号不在 peo数组中,且他出现的次数刚好比 n 小 1,说明该编号即为法官。

对于成员判断,Python 提供了 in, not in 等成员运算符, C++ 使用 find, count 等函数即可。

Python版本

C++版本


复杂度分析

  • 时间复杂度:O(N)。 其中 ntrust 数组的长度, 在本题中需要遍历两次:存储两类人员编号以及存储法官编号的数组,其中后者是前者的子集,且大O计数忽略常数,故取较大数组长度。

  • 空间复杂度:   O(N)。其中 n 是人员个数,本题中用到三个数组,但哈希数组的长度最大,表示的是所有人的人员编号,因此取较大数组;


997. 找到小镇的法官的评论 (共 条)

分享到微博请遵守国家法律