从房客列表中移除不认识 N 人的人

Question

在一次编码面试中，有人问我这个问题，我一辈子都想不出来。

输入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

N=2

输出

1->2,3,5

2->1,3,5

3->1,2,5

5->1,2,3

基本上，每个列表都是主要值认识的人(0知道1(，如果他们不认识N个人，他们将从来宾列表和其他成员列表中删除。删除那些不认识足够多的人后，记录聚会的状态

我目前的模型：

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);
}
public static void UpdateGuestList(List<Guest> guests, int needToKnow)
{

}

Answer 1

我建议使用一种稍微不同的数据结构：Dictionary<int, HashSet<int>>，其中Key是访客，而Value包含已知的人。在这里，我们应该删除和项目，我们可以通过哈希更有效地做到这一点：

var data = new Dictionary<int, HashSet<int>>() {
{ 0, new HashSet<int>() { 1 } },
{ 1, new HashSet<int>() { 0, 2, 3, 4, 5 } },
{ 2, new HashSet<int>() { 1, 3, 4, 5 } },
{ 3, new HashSet<int>() { 1, 2, 4, 5 } },
{ 4, new HashSet<int>() { 0 } },
{ 5, new HashSet<int>() { 1, 2, 3, 4 } }, 
};
int N = 2;

请注意，我们应该在循环中删除来宾：如果我们删除来宾#0，则其他一些潜在的现在了解#)的客人可以比N:了解更少的人

while (true) {
var remove = data
.Where(pair => pair.Value.Count < N)
.Select(pair => pair.Key)
.ToList();

if (remove.Count <= 0)
break;
foreach (int key in remove) {
data.Remove(key);
foreach (var value in data.Values)
value.Remove(key);
}
}

是时候提供一些报告了：

var report = string.Join(Environment.NewLine, data
.OrderBy(pair => pair.Key)
.Select(pair => $"{pair.Key} -> {string.Join(", ", pair.Value.OrderBy(item => item))}")
);
Console.Write(report);

输出：

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

请你自己摆弄

Answer 2

我认为你应该首先保存一个没有足够朋友的人的列表，然后使用迭代循环来遍历他们。例如，由于0没有足够的朋友，您可以查看他们是谁的朋友。你看到他们是1的朋友，所以你转到1的列表并删除0。然后检查1是否有足够的朋友。如果他们没有，你会看到1是谁的朋友，并从他们的列表中删除1，以此类推。然后你对4也这样做。

你不需要删除节点，关键是它们会告诉你应该删除哪些列表中的节点。然后让循环沿着路径运行。之后，你只需再次遍历整个客人列表，看看谁还有足够的朋友。