JavaScript 明星问题

明星问题

题目：

有 n 个人，其中一个明星和 n-1 个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现有一个
函数 foo(A, B)，若 A 认识 B 返回 true，若 A 不认识 B 返回 false，试设计一种算法找出明星，并给出时间复杂度。


思路：

（1）第一种方法我们可以直接使用双层循环遍历的方式，每一个人都和其他人进行判断，如果一个人谁都不认识，那么他就是明星。
    这一种方法的时间复杂度为 O(n^2)。

（2）上一种方法没有充分利用题目所给的条件，其实我们每一次比较，都可以排除一个人的可能。比如如果 A 认识 B，那么说明
    A 就不会是明星，因此 A 就可以从数组中移除。如果 A 不认识 B，那么说明 B 不可能是明星，因此 B 就可以从数组中移
    除。因此每一次判断都能够减少一个可能性，我们只需要从数组从前往后进行遍历，每次移除一个不可能的人，直到数组中只剩
    一人为止，那么这个人就是明星。这一种方法的时间复杂度为 O(n)。

详细资料可以参考： 《一个明星和 n-1 个群众》

更多面试题

如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。

这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！