英文:
Find lowest ancestor in a list
问题
我有一个存储用户的对象数组，其中有一个键为Manager。我想找到列表中任意两个用户ID的最低Manager。对象的数量可能很大，因此寻找一个高效的解决方案。
例如，对于以下列表：
[
{
"User": "John",
"Manager": "Jake"
},
{
"User": "Ben",
"Manager": "John"
},
{
"User": "Steve",
"Manager": "John"
}...
]
Ben和Steve的共同Manager是John。但是，对于Ben和John，Manager是Jake。
我的初步想法包括将列表转换为树，然后找到最低的公共祖先，但我怀疑可能存在更好的方法。
英文:
I have an array of objects storing users which have Manager as a key. I want to find lowest Manager for any of the two user ids in the list.The number of objects would be large, hence looking for an efficient solution.
For Example, for below list,
[
{
"User": "John",
"Manager": "Jake"
},
{
"User": "Ben",
"Manager": "John"
},
{
"User": "Steve",
"Manager": "John"
}...
]
The common Manager for Ben & Steve would be John. However, for Ben & John would be Jake.
My initial thoughts include converting list to a tree & then finding the lowest common ancestor, but I suspect there probably is a better approach.
答案1
得分: 2
@ShihabRahman's现已删除的答案是高效的，但由于将用户而不是管理人员视为路径的一部分，因此未能完全起作用。改为将管理人员作为路径的一部分，它将起作用：
users = [
{"User": "John", "Manager": "Jake"},
{"User": "Ben", "Manager": "John"},
{"User": "Steve", "Manager": "John"}
]
def find_lowest_common_manager(users, user1, user2):
# 建立将每个用户映射到其经理的字典
managers = {u['User']: u['Manager'] for u in users}
# 创建一个集合来存储从user1到其经理的路径
path = set()
# 从user1开始遍历经理层次结构并存储路径
while user1 in managers:
user1 = managers[user1]
path.add(user1)
# 从user2开始遍历经理层次结构，直到找到共同的经理
while user2 in managers:
user2 = managers[user2]
if user2 in path:
# 找到共同的经理
return user2
# 未找到共同的经理
return None
print(find_lowest_common_manager(users, 'Ben', 'Steve'))
print(find_lowest_common_manager(users, 'Ben', 'John'))
这将输出：
John
Jake
演示链接：https://replit.com/@blhsing/ScientificHumongousGigabyte
英文:
@ShihabRahman's now deleted answer is efficient but didn't quite work since users, not managers, were considered part of the path. Make managers part of the path instead and it would work:
users = [
{"User": "John", "Manager": "Jake"},
{"User": "Ben", "Manager": "John"},
{"User": "Steve", "Manager": "John"}
]
def find_lowest_common_manager(users, user1, user2):
# Build a dictionary mapping each user to their manager
managers = {u['User']: u['Manager'] for u in users}
# Create a set to store the path from user1 to their manager
path = set()
# Traverse up the manager hierarchy from user1 and store the path
while user1 in managers:
user1 = managers[user1]
path.add(user1)
# Traverse up the manager hierarchy from user2 until a common manager is found
while user2 in managers:
user2 = managers[user2]
if user2 in path:
# Found a common manager
return user2
# No common manager found
return None
print(find_lowest_common_manager(users, 'Ben', 'Steve'))
print(find_lowest_common_manager(users, 'Ben', 'John'))
This outputs:
John
Jake
Demo: https://replit.com/@blhsing/ScientificHumongousGigabyte
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论