基于二维数组查找孤立城市的高效实现方案问询

问题定义 #

给定二维数组List，外层数组的索引为城市ID，内层数组元素为该城市拥有的公路ID。孤立城市的判定标准是：该城市的所有公路ID在整个数组中仅出现一次（无其他城市共享这些公路）。例如输入List = [[1,2],[4,5,8],[1,2,3],[1,3]]时，城市1（索引1）的公路4、5、8均只出现一次，因此返回1；无符合条件的城市则返回-1。

高效解决方案思路 #

四层嵌套循环的时间复杂度为O(M²K²)（M为城市数，K为单城市平均公路数），效率极低。我们可以通过哈希表统计公路出现次数的方式将时间复杂度降到O(N + MK)（N为所有公路的总数量），具体步骤如下：

• 第一步：遍历所有城市的所有公路，用字典记录每个公路ID的出现次数。
• 第二步：逐个检查每个城市，验证该城市的所有公路的出现次数是否全为1。第一个满足条件的城市ID即为答案；若全部城市都不满足，返回-1。

代码示例（Python） #

def findIsolatedCity(city_roads):
    # 统计所有公路的出现次数
    road_count = {}
    for roads in city_roads:
        for road in roads:
            road_count[road] = road_count.get(road, 0) + 1
    
    # 遍历每个城市，检查是否符合孤立条件
    for city_id, roads in enumerate(city_roads):
        is_isolated = True
        for road in roads:
            if road_count[road] != 1:
                is_isolated = False
                break
        if is_isolated:
            return city_id
    # 无符合条件的城市
    return -1

# 测试示例
test_list = [[1,2],[4,5,8],[1,2,3],[1,3]]
print(findIsolatedCity(test_list))  # 输出：1

复杂度说明 #

• 统计公路次数：遍历所有公路一次，时间复杂度O(N)，N为总公路数。
• 检查城市：遍历每个城市的每个公路，时间复杂度O(M*K)，M为城市数，K为单城市平均公路数。
• 空间复杂度O(R)，R为不同公路的数量，用于存储公路出现次数的字典。

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