阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      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前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题,也有一些大公司的面试图,可以让你面试更加顺利。

      面试题
      HTMLCSSJavaScript
      jQueryVue.jsReact
      算法HTTPBabel
      BootStrapElectronGulp
      Node.js前端经验相关前端综合
      Webpack微信小程序-

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

      目录
      目录