690.员工的重要性

Problem: 690. 员工的重要性

思路

使用哈希表在常数时间获取id对应的employee，使用dfs搜索即可。

复杂度

• 时间复杂度: $O(n)$，所有操作都是线性时间，HashMap查找只需要常数时间。
• 空间复杂度: $O(n)$，HashMap的空间复杂度。

注意的点

TreeMap的时间复杂度要比HashMap要高。

Code

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    Map<Integer, Employee> m = new HashMap<>();
    
    public int getImportance(List<Employee> employees, int id) {
        int n = employees.size();
        for (Employee e: employees) {
            m.put(e.id, e);
        }
        Employee start = m.get(id);
        return cal(start);
    }

    public int cal(Employee e) {
        int ans = e.importance;
        for (Integer i : e.subordinates) {
            ans += cal(m.get(i));
        }
        return ans;
    }
}