面试算法题：筛选满足社交人数要求的宾客名单

问题描述 #

给定宾客的社交关系列表（如0 -> 1表示0认识1），给定阈值N=2，需要：

• 移除当前认识人数不足N的宾客
• 将被移除的宾客从剩余宾客的社交名单中删除
• 重复上述过程，直到没有宾客需要被移除为止（移除部分宾客后，剩余宾客的好友数可能降到阈值以下）

输入示例：

0 -> 1
1 -> 0,2,3,4,5
2 -> 1,3,4,5
3 -> 1,2,4,5
4 -> 0
5 -> 1,2,3,4

C# 解决方案 #

以下是完成UpdateGuestList方法的实现：

public class Guest
{
    public int Id { get; set; }
    public IList<int> Friends { get; set; }
}

public static void Main(string[] args)
{
    var guest0 = new Guest
    {
        Id = 0,
        Friends = new List<int> {1}
    };
    
    var guest1 = new Guest
    {
        Id = 1,
        Friends = new List<int> {0,2,3,4,5}
    };
    
    var guest2 = new Guest
    {
        Id = 2,
        Friends = new List<int> {1, 3, 4,5}
    };
    
    var guest3 = new Guest
    {
        Id = 3,
        Friends = new List<int> {1,2,4,5}
    };
    
    var guest4 = new Guest
    {
        Id = 4,
        Friends = new List<int> {0}
    };
    
    var guest5 = new Guest
    {
        Id = 5,
        Friends = new List<int> {1,2,3,4}
    };
    
    var guestList = new List<Guest>{guest0, guest1, guest2, guest3, guest4, guest5};
    
    UpdateGuestList(guestList, 2);
    
    // 输出处理结果验证
    foreach (var guest in guestList)
    {
        Console.WriteLine($"{guest.Id} -> {string.Join(",", guest.Friends)}");
    }
}

public static void UpdateGuestList(List<Guest> guests, int needToKnow)
{
    // 用HashSet存储当前有效的宾客ID，便于快速查询
    var validGuests = new HashSet<int>(guests.Select(g => g.Id));
    
    bool hasRemoved;
    do
    {
        hasRemoved = false;
        // 找出当前需要移除的宾客ID：有效宾客中好友数（仅统计有效好友）不足needToKnow的
        var toRemove = validGuests
            .Where(id => 
                guests.First(g => g.Id == id).Friends.Count(f => validGuests.Contains(f)) < needToKnow)
            .ToList();
        
        if (toRemove.Any())
        {
            hasRemoved = true;
            // 从有效集合中移除这些宾客
            foreach (var id in toRemove)
            {
                validGuests.Remove(id);
            }
            
            // 更新剩余宾客的好友列表，移除已被删除的ID
            foreach (var guest in guests.Where(g => validGuests.Contains(g.Id)))
            {
                // 过滤掉不在有效集合中的好友
                guest.Friends = guest.Friends.Where(f => validGuests.Contains(f)).ToList();
            }
        }
    } while (hasRemoved);
    
    // 最后过滤原列表，只保留有效宾客
    guests.RemoveAll(g => !validGuests.Contains(g.Id));
}

实现说明 #

1. 有效宾客跟踪：使用HashSet<int>存储当前有效的宾客ID，保证O(1)时间复杂度的查询效率。
2. 循环处理：因为移除宾客可能导致其他宾客的好友数降到阈值以下，所以需要循环处理直到没有宾客被移除。
3. 移除逻辑：
   • 每次循环计算当前有效宾客的实际好友数（仅统计仍在有效集合中的好友）
   • 标记需要移除的宾客，从有效集合中删除
   • 更新剩余宾客的好友列表，过滤掉已被移除的ID
4. 最终整理：过滤原宾客列表，只保留有效宾客，完成处理。

示例输出 #

运行代码后，输出结果为：

1 -> 2,3,5
2 -> 1,3,5
3 -> 1,2,5
5 -> 1,2,3

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