提问人：LukeMahn 提问时间：10/13/2022 更新时间：10/13/2022 访问量：45
使用 2D 阵列查找孤立的城市
Finding isolated city using 2D array
问：
我得到了一个二维数组，其中城市的 ID 是外部数组的索引，内部数组中的数字表示高速公路 ID。
List = [[1,2],[4,5,8],[1,2,3],[1,3]]
我试图找到一个孤立的城市，所以没有高速公路将其连接到另一个城市（其中的所有高速公路在列表中都是唯一的，并且只出现一次？在上面的示例中，带有 [4,5,8] 的城市 1 将被隔离，因此对函数 findIsolatedCity（List） 的调用应返回 1。如果找不到城市，则该函数返回 -1。
我尝试用伪代码实现解决方案，但我所能想到的效率相当低（4 个嵌套循环）。有谁知道更有效的解决方案？
function findIsolatedCity(List)
isolated_city = -1
for city in range(len(List):
highway_count = 0
list_unique_highways = []
for highway in List[city]:
// check if the highway connects to any other city
for city_2 in range(len(List)): // iterate over all cities
for highway_2 in List[city_2]: // iterate over all highways in other cities
if highway == highway_2:
highway_count += 1
if highway_count == 1:
list_unique_highways.append(highway)
if length(list_) == length(List[city]):
isolated_city = city
return isolated_city
return isolated_city
答：
2赞
Andrej Kesely
10/13/2022
#1
根据@user3386109的评论，这是 Python 中的解决方案：
from collections import Counter
cities = [[1, 2], [4, 5, 8], [1, 2, 3], [1, 3]]
def find_isolated_cities(cities):
cnt = Counter(h for c in cities for h in c)
return sum(all(cnt[h] == 1 for h in c) for c in cities)
print(find_isolated_cities(cities))
指纹：
1
首先，我们构造计数器，计算所有子列表中每个 higway 的数量，然后计算所有 higway 计数等于 1 的城市。
评论