class Solution(object): def getImportance(self, employees, id): employees.sort(key=lambda x: x.id) res = 0 subs = [employees[id-1]] for sub in subs: res += sub.importance subs += [employees[x-1] for x in sub.subordinates ] return res
Edited: sort the list first, complexity would be n log(n) + n
nice and tidy
@shaynexwang How can you guarantee that
[employees[id-1]] is the location of the first employee? The question does not explicitly say
employees will be sorted by
id. In fact you cannot even guarantee that
employees has enough items to index at
[id-1]. The problem does not say that employee ids span 1 to N. If this code passed OJ, I think more test cases need to be added.
@david120 you are right we cannot assume the list is sorted, we do need a better test. I think a non-empty list of Employee is assumed, otherwise you'd get an index error anyway. If the employee list is empty then what should be given as an employee id?
@shaynexwang Yes I think you can assume
employees is not empty. But you've also assumed that the employee ids are the same as the indices of the list. For example, your code would not pass
employees = [ [10,1,], [20, 1, ] ] id = 10
because there's no way we can look
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.