在图中找到下属居住在多个城市的经理电话号码的最佳方法

Question

我正在试图找到所有经理的电话号码，他们的直接报告层次结构都生活在超过一个城市的O(n)时间复杂性中。下面是我的方法，它与时间复杂性O(M*N)，其中M是经理的数目，N是就业人数。有谁能帮我解决这个问题的O(N)方案吗？

import java.util.*;

public class EmployeePhoneNums {
    public static void main(String[] args) {            
        String[][] emps2 = new String[][]{
     //"EmployeeID", "ManagerID", "City", "Phone number"
                {"e1", "e1", "SF", "phone-1"},
                {"e2", "e1", "SF", "phone-2"},
                {"e3", "e1", "SF", "phone-3"},
                {"e4", "e2", "SF", "phone-4"},
                {"e5", "e2", "PH", "phone-5"},
                {"e6", "e3", "NY", "phone-6"}                   
        };
        Map<String, String> phoneNums = getmanagerPhoneNums(emps2);
        System.out.println(phoneNums);
    }

    public static Map<String, String> getmanagerPhoneNums(String[][] input) {
        Map<String, String> managerPhoneNums = new HashMap<>();
        Map<String, String> phoneMap = new HashMap<>();
        Map<String, String> cityMap = new HashMap<>();
        Map<String, Set<String>> mgrEmps = new HashMap<>();
        Set<String> managers = new LinkedHashSet<>();
        for (String[] emp : input) {
            phoneMap.put(emp[0], emp[3]);
            cityMap.put(emp[0], emp[2]);
            managers.add(emp[1]);
            if (emp[0].equals(emp[1]))
                continue;
            else {
                mgrEmps.putIfAbsent(emp[1], new HashSet<>());
                mgrEmps.get(emp[1]).add(emp[0]);
            }
        }
        System.out.println(mgrEmps);
        Queue<String> managersQ = new LinkedList<>(managers);
        while (!managersQ.isEmpty()) {
            String manager = managersQ.poll();
            bfs(manager, mgrEmps, phoneMap, cityMap, managerPhoneNums);
        }
        return managerPhoneNums;
    }

    public static void bfs(String manager, Map<String, Set<String>> mgrEmps, Map<String, String> phoneMap, Map<String, String> cityMap, Map<String, String> resultPhoneNums) {
        Queue<String> reportees = new LinkedList<>();
        if (mgrEmps.containsKey(manager)) reportees.addAll(mgrEmps.get(manager));
        Set<String> cities = new HashSet<>();
        while (!reportees.isEmpty()) {
            int size = reportees.size();
            for (int i = 0; i < size; i++) {
                String emp = reportees.poll();
                if (mgrEmps.get(emp) != null && mgrEmps.get(emp).size() > 0) reportees.addAll(mgrEmps.get(emp));
                cities.add(cityMap.get(emp));
                if (cities.size() > 1) break;
            }
            if (cities.size() > 1) {
                resultPhoneNums.put(manager, phoneMap.get(manager));
                break;
            }
        }
    }
}

Answer 1

对于这个问题，我们可以很好地将员工之间的关系建模为 (或DAG)。

这样就可以在班轮时间O(n)中找到拥有至少来自两个不同城市的下属的经理。

对于这个任务，我们不需要区分作业卷，这意味着我们可以假设每个员工都可能有一个经理和下属，图的顶点将由Employee类表示。

在这个图中不会有循环，因为根据样本数据，每个员工最多只能有一个经理(我将忽略员工e1的情况，因为从这个问题的角度来看，它本身就是老板)，而连接的顶点则来自所谓的N-ary树。

也可能有一种情况，当有几组员工没有联系，他们将形成所谓的。为了确保在图包含多个连通组件时检查所有顶点，我们需要遍历所有顶点的集合，并对尚未遇到的每个顶点触发遍历算法。

为了理解遍历的逻辑，让我们考虑下面的员工图。

​

​

正如您所看到的，Employe-1(与id1)和Employe-3(与id3)都被标记为绿色的勾号，表示他们有居住在多个城市的下属。橙色箭头代表员工-下属，黑色箭头-遍历方向。

假设遍历从Employee-1开始。为了遍历图表，我们将使用 (简称DFS)，为了我们的目的稍微调整一下。在内部，它使用堆栈数据结构(在下面的代码中简单表示为stack)。在每个分支中，当我们碰到没有下属的员工时，我们需要能够反向传播属性(这就是我提到的调整)，为此我们将使用另一个堆栈(表示为isBeingVisited，这意味着我们还没有检查它包含的员工，因为我们正在遍历他们的下属)。

因此，我们首先在stack顶部分配Employee-1。遍历的每一步都从从stack中移除元素开始。最初，我们只有Employee-1，它正在被移除，并且由于它有下属，它将被放在堆栈isBeingVisited的顶部，它的下属Employee-2和Employee-3将被推到stack上。

在第二步开始时，我们在stack的顶部有员工-3。它将被移除并分配到isBeingVisited顶部，而它的下属员工-4和雇员--5将被推到stack上。

第三步将从stack中移除5名员工，将其推到isBeingVisited上，并在stack上分配其下属雇员6。

在这里，我们已经到了N-ary树的左边，它意味着两件事:Employe-6没有机会出现在结果列表中(它们是幸运的下属)，我们不需要将它们推入isBeingVisited (我们已经完成了)，但是作为告诉它的管理人员离开哪里的最后一步。因此，我们开始向后移动，传播属性，即boolaen字段isSelected (表示该雇员是否与给定的标准匹配)，或一组城市(更详细的信息请参见propagateSelection()的实现)。

注释:代码逻辑中的与DFS-实现解耦，而堆栈isBeingVisited正在一次性处理。

简而言之，方法getSelectedEmployee()通过调用DFS-implementation，方法dfs()来激发遍历，只要它遇到了以前从未见过的顶点。当dfs()完成时，方法select()向后(从从属到管理器)执行遍历，传播下属的属性并填充结果列表。

图的实现可能如下所示。

public static class EmployeeGraph {
    
    private Map<String, Employee> employeeById = new HashMap<>();
    
    public List<Employee> getSelectedEmployee() {
        List<Employee> result = new ArrayList<>();  // will store the managers having subordinates from more than one city
        Deque<Employee> stack = new ArrayDeque<>(); // will be used for performing traversal in the DFS implementation
        Set<Employee> seen = new HashSet<>();       // is meant to store every encountered vertex
        
        for (Employee next : employeeById.values()) {
            if (!seen.contains(next)) {
                stack.push(next);
                seen.add(next);
                dfs(result, stack, seen);
            }
        }
        return result;
    }
    
    private void dfs(List<Employee> result, Deque<Employee> stack, Set<Employee> seen) { // DFS implementation
        Deque<Employee> isBeingVisited = new ArrayDeque<>(); // stack of vertices that are being visited, i.e. managers which subordinates haven't been fully examined
        
        while (!stack.isEmpty()) {
            Employee current = stack.pop();
            List<Employee> subordinates = current.getSubordinates();
            
            if (subordinates.isEmpty()) {
                current.propagateSelection(); // share the city with a direct manager
            } else {
                isBeingVisited.push(current);
                for (Employee subordinate: current.getSubordinates()) {
                    if (seen.add(subordinate)) stack.push(subordinate); // allocating subordinates on the stack
                }
            }
        }
        select(result, isBeingVisited); // examining the properties of managers that has been visited
    }
    
    private void select(List<Employee> result, Deque<Employee> isBeingVisited) {
        while (!isBeingVisited.isEmpty()) {
            Employee manager = isBeingVisited.pop();
            if (manager.isSelected()) result.add(manager); // if manager is marked as selected - add to the result list
            manager.propagateSelection();                  // propagating the properties to the direct manager (if any)
        }
    }
    
    // NOT a part of the Algorithm - convenience-method for initializing the graph by parsing string arguments into instances of employee
    public void addEmployee(String... args) {
        if (args.length == 1) {
            employeeById.computeIfAbsent(args[0], Employee::new);
        } else if (args.length == 4) {
            Employee manager = args[1] != null ? employeeById.computeIfAbsent(args[1], Employee::new) : null;
            
            if (employeeById.containsKey(args[0])) {
                Employee employee = employeeById.get(args[0]);
                
                employee.setManager(manager)
                    .setCity(args[2])
                    .setPhone(args[3]);
            } else {
                employeeById.put(args[0], new Employee(args[0],manager, args[2], args[3]));
            }
            
            if (args[1] != null) {
                manager.addSubordinate(employeeById.get(args[0]));
            }
        } else {
            throw new IllegalArgumentException();
        }
    }
    
    public static class Employee {
        private String id;
        private String city;
        private String phone;
        private Employee manager;
        private List<Employee> subordinates = new ArrayList<>();
        
        private Set<String> subordinateCities = new HashSet<>();
        private boolean isSelected;
        
        public Employee(String id) {
            this.id = id;
        }
        
        public Employee(String id, Employee manager, String city, String phone) {
            this.id = id;
            this.city = city;
            this.phone = phone;
            this.manager = manager;
        }
        
        public void addSubordinate(Employee employee) {
            subordinates.add(employee);
        }
        
        public void propagateSelection() {
            if (manager == null) return;
            
            if (isSelected) {
                manager.setSelected();
            } else {
                shareSubordinateCitiesWithManager();
                manager.trySelect();
            }
        }
        
        public void shareSubordinateCitiesWithManager() {
            Set<String> managersSubCities = manager.subordinateCities;
            managersSubCities.addAll(this.subordinateCities);
            managersSubCities.add(this.city);
        }
        
        public void trySelect() {
            if (subordinateCities.size() >= 2) {
                setSelected();
            }
        }
        
        public List<Employee> getSubordinates() {
            return subordinates;
        }

        public String getPhone() {
            return phone;
        }
        
        public void setSelected() {
            isSelected = true;
        }
        
        public boolean isSelected() {
            return isSelected;
        }

        public Employee setCity(String city) {
            this.city = city;
            return this;
        }

        public Employee setPhone(String phone) {
            this.phone = phone;
            return this;
        }

        public Employee setManager(Employee manager) {
            this.manager = manager;
            return this;
        }
    }
}

注释:如文档所建议的那样，作为堆栈数据结构的实现，我们需要使用实现Deque接口的类(类Stack是遗留的，不应该使用)。当我们需要一个通用的Deque实现时，最好的选择是一个ArrayDeque__，它是由普通数组支持的，顾名思义，它的方法比LinkedList__的相应方法要快得多。您可以在代码中遇到LinkedList的唯一原因，尤其是在实现图遍历算法时，是因为从Java的早期开始，它是Queue和Deque接口的唯一通用实现，直到ArrayDeque 6在JDK中被引入。

main()

public static void main(String[] args) {
    String[][] emps = new String[][]{
        //"EmployeeID", "ManagerID", "City", "Phone number"
        {"e1", null, "SF", "phone-1"},
        {"e2", "e1", "SF", "phone-2"},
        {"e3", "e1", "SF", "phone-3"},
        {"e4", "e2", "SF", "phone-4"},
        {"e5", "e2", "PH", "phone-5"},
        {"e6", "e3", "NY", "phone-6"}
    };

    EmployeeGraph graph = new EmployeeGraph();
    for (String[] arr: emps) graph.addEmployee(arr); // initializing the graph
    
    graph.getSelectedEmployee().forEach(e -> System.out.println(e.getPhone())); // printing the result - phones of the selected managers
}

输出：

phone-2
phone-1

Answer 2

这里有一种可能的方法：

managers

• Define

1. 维护两个映射-一个用于所有员工，一个用于为经理提供一个类/DS --信息、报告者、属于
2. 的一组不同的城市。这两个映射可以在O(N)
3. 中构建，一旦您有了它，就可以迭代(在O(N)中)来找到所有被报告城市集大小大于1

的经理。

定义类来表示经理-记者信息，如下所示

import java.util.*;

public class MgrReportees {
    private String mngr_id = null;
    private String[] mngr_info = null;
    private List<String> reportee_ids  = new ArrayList<>();
    private Map<String,String[]> reportee_info = new HashMap<>();
    private Set<String> reportee_city = new LinkedHashSet<>();

    public void process(String[] emp, Map<String, String[]> all_emp) {
        this.mngr_id = emp[1];
        if(emp[0].equals(emp[1])) { // this one is manager's info
            this.mngr_info = emp;
        }else {
            if(all_emp.containsKey(emp[1])) { // if available, then update manager's ifo
                this.mngr_info = all_emp.get(emp[1]);
            }
            if(!reportee_info.containsKey(emp[0])) {
                reportee_ids.add(emp[0]);
            }
            reportee_info.put(emp[0], emp);
            reportee_city.add(emp[2]);
        }
    }

    public String getMngr_id() {
        return mngr_id;
    }

    public String[] getMngr_info() {
        return mngr_info;
    }

    public List<String> getReportee_ids() {
        return reportee_ids;
    }

    public Map<String, String[]> getReportee_info() {
        return reportee_info;
    }

    public String[] getReportee_info(String reportee_id) {
        return reportee_info.get(reportee_id);
    }

    public Set<String> getReportee_cities() {
        return reportee_city;
    }
}

下面是如何构建经理信息地图，注意这两张地图--所有员工和经理

public static Map<String, MgrReportees> constructManagerReportees(String[][] input) {
        Map<String, MgrReportees> mngr_registry = new HashMap<>();
        Map<String, String[]> employees_registry = new HashMap<>();
        for (String[] emp : input) {
            employees_registry.put(emp[0],emp );
            MgrReportees mgr = mngr_registry.containsKey(emp[1]) ? mngr_registry.get(emp[1])  : new MgrReportees();
            mgr.process(emp, employees_registry);
            mngr_registry.put(emp[1],mgr);
        }

        return mngr_registry;
    }

最后，将其称为&基本城市规模检查：

    public static void main(String[] args) {
        String[][] emps2 = new String[][]{
                //"EmployeeID", "ManagerID", "City", "Phone number"
                {"e1", "e1", "SF", "phone-1"},
                {"e2", "e1", "SF", "phone-2"},
                {"e3", "e1", "SF", "phone-3"},
                {"e4", "e2", "SF", "phone-4"},
                {"e5", "e2", "PH", "phone-5"},
                {"e6", "e3", "NY", "phone-6"}
        };
        Map<String, MgrReportees> mgrs = constructManagerReportees(emps2);
        // Find manager's phone with reportees in more than 1 city
        System.out.println("Finding Managers with reportees in more tha 1 city");
        for (Map.Entry<String,MgrReportees> entry : mgrs.entrySet()) {
            MgrReportees r = entry.getValue();
            int cityCount = r.getReportee_cities().size();
            if( cityCount > 1) {
                System.out.println(String.format("Found Manager Id = %s , Mngr Phone = %s, Reportees City Count = %d "
                        ,entry.getKey()
                        ,r.getMngr_info()[3]
                        ,cityCount));
            }
        }

        System.out.println("Done");
    }

对于给定的样本数据，输出将是

Finding Managers with reportees in more tha 1 city
Found Manager Id = e2 , Mngr Phone = phone-2, Reportees City Count = 2 
Done

希望这能有所帮助

Answer 3

使用employee类和java 8方法完成该操作：

public class EmployeePhoneNums {
    
    public static void main(String[] args) {            
        List<Employee> emps2 = List.of(
                new Employee("e1", "e1", "SF", "phone-1"),
                new Employee("e2", "e1", "SF", "phone-2"),
                new Employee("e3", "e1", "SF", "phone-3"),
                new Employee("e4", "e2", "SF", "phone-4"),
                new Employee("e5", "e2", "PH", "phone-5"),
                new Employee("e6", "e3", "NY", "phone-6"));
        Map<String, String> managerPhoneNums = emps2.stream().collect(Collectors.toMap(Employee::getEmpolyeeId, Employee::getPhoneNumber));
        Map<String, Set<String>> managerAndCityOfEmployee = emps2.stream().filter(e -> !e.getEmpolyeeId().equals(e.getManagerId())).collect(Collectors.groupingBy(Employee::getManagerId, Collectors.mapping(Employee::getCity, Collectors.toSet())));
        List<String> resultManager = managerAndCityOfEmployee.entrySet().stream().filter(m -> m.getValue().size() > 1).map(m -> m.getKey()).collect(Collectors.toList());
        resultManager.forEach(rm -> System.out.println(rm + " : " + managerPhoneNums.get(rm)));
    
    }
}

class Employee {
    String empolyeeId;
    String managerId;
    String city;
    String phoneNumber;
    
    public Employee(String empolyeeId, String managerId, String city, String phoneNumber) {
        super();
        this.empolyeeId = empolyeeId;
        this.managerId = managerId;
        this.city = city;
        this.phoneNumber = phoneNumber;
    }

    public String getEmpolyeeId() {
        return empolyeeId;
    }

    public void setEmpolyeeId(String empolyeeId) {
        this.empolyeeId = empolyeeId;
    }

    public String getManagerId() {
        return managerId;
    }

    public void setManagerId(String managerId) {
        this.managerId = managerId;
    }

    public String getCity() {
        return city;
    }

    public void setCity(String city) {
        this.city = city;
    }

    public String getPhoneNumber() {
        return phoneNumber;
    }

    public void setPhoneNumber(String phoneNumber) {
        this.phoneNumber = phoneNumber;
    }

}

PS:不明白为什么e1在您的输出中，他所有的员工都生活在SF中。