寻求O(n)时间复杂度的下属跨多城市经理手机号查询解法

首先明确需求：仅统计直接汇报给经理的第一级下属的居住城市数量，若超过1个，则记录该经理的手机号。

核心思路 #

1. 一次遍历所有员工，建立两个关键映射：
   • 员工ID与手机号的映射，快速获取经理的手机号
   • 经理ID与下属城市集合的映射，实时统计每个经理的直接下属城市数量
2. 遍历过程中，一旦发现某个经理的下属城市数量超过1，直接标记该经理符合条件（无需后续重复统计）
3. 最后从映射中提取所有符合条件的经理手机号，全程仅需O(n)时间（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); // 预期输出：{e2=phone-2}
    }

    public static Map<String, String> getManagerPhoneNums(String[][] input) {
        Map<String, String> empPhoneMap = new HashMap<>();
        // 存储经理ID对应的下属城市集合，同时用集合记录已符合条件的经理，避免重复处理
        Map<String, Set<String>> mgrDirectCities = new HashMap<>();
        Set<String> qualifiedManagers = new HashSet<>();

        for (String[] emp : input) {
            String empId = emp[0];
            String managerId = emp[1];
            String city = emp[2];
            String phone = emp[3];

            // 记录员工手机号（经理本身也是员工）
            empPhoneMap.put(empId, phone);

            // 跳过自己管理自己的情况（无需统计自身）
            if (empId.equals(managerId)) {
                continue;
            }

            // 该经理已符合条件，无需再处理其下属
            if (qualifiedManagers.contains(managerId)) {
                continue;
            }

            // 获取该经理的下属城市集合，不存在则创建
            Set<String> cities = mgrDirectCities.computeIfAbsent(managerId, k -> new HashSet<>());
            cities.add(city);
            // 城市数量超过1，标记为符合条件，同时移除映射节省空间
            if (cities.size() > 1) {
                qualifiedManagers.add(managerId);
                mgrDirectCities.remove(managerId);
            }
        }

        // 收集符合条件的经理手机号
        Map<String, String> result = new HashMap<>();
        for (String manager : qualifiedManagers) {
            result.put(manager, empPhoneMap.get(manager));
        }
        return result;
    }
}

复杂度说明 #

• 遍历员工数组是O(n)，每个员工的哈希表增查操作都是O(1)平均时间
• 最后收集结果的遍历是O(k)，k为符合条件的经理数量，k ≤ n
• 整体时间复杂度为O(n)，空间复杂度为O(n)（存储映射和集合）

内容的提问来源于stack exchange，提问作者OTUser