算法题 —— 寻找明星

我会带着你远行 2022-05-24 03:27 131阅读 0赞

前段时间在现场面试的时候碰到的题目，做下总结。

#### 题目设定 ####

--------------------

有 N 个人，其中有1个人是明星，其他 N-1 个人是群众，所有群众都认识明星，明星不认识任何群众，群众的互相认识关系未知，现有一个函数 `Boolean recognize(A, B)`，返回 true 表示 A 认识 B，返回 false 表示 A 不认识 B。设计一个最优算法找出明星（假定这N个人是 arr\[N\]）。

#### 常规思路 ####

--------------------

先讲一个常规思路，任选一人作为 A，将余下的人依次代入 B，当 A 不认识 B 时，将 B 换一人，当 A 认识 B 时，将 A 换一人，这样找到一个 A 对所有 B 都不认识，则这个 A 是明星。  
  很容易看出，选 A 的过程是一个循环，排 B 的过程是一个循环，此算法是一个嵌套循环，时间复杂度是 O(n)。

#### 理清条件 ####

--------------------

在设计算法时，让我们先来理清楚现有条件，在调用 `recognize(A, B)` 这个函数，有下面的两种返回值：

1.  返回 true，A 认识 B，那么我们可以确定 **A 肯定不是明星**；
2.  返回 false，A 不认识 B，那么我们可以确定 **B 肯定不是明星**。

从上面的两个结果，我们可以知道，**每调用一次 `recognize(A, B)` 这个函数，肯定可以判定一个人不是明星**。

#### 思路迁移 ####

--------------------

理清楚题目给的条件后，我们可以先来看一个关于 N 个数找最大值的问题，（伪）代码如下：

max = arr[0];
    for (int i = 1; i < arr.length; i ++) {
        if(arr[i] > max)
            max = arr[i];
    }
    return man;

我们来看下 `if(arr[i] > max) {...}` 这个条件判断，同样是一个条件两个结果：

1.  返回 true，arr\[i\] 比之前存的值大，那么**之前存的值肯定不是最大值**；
2.  返回 false，arr\[i\] 比之前存的值小，那么**当前值肯定不是最大值**。

> ps: 假设即 `if(arr[1] > max) {...}`，若返回 true，那么 arr\[0\] 肯定不是最大值，返回 false，那么 arr\[1\] 肯定不是最大值。

同样的一个条件，排除一个候选者。怎么样，有新思路了吗？

#### 最优思路 ####

--------------------

思路与找最大值的思路一致，不啰嗦了，直接贴上（伪）代码：

star = arr[0];
    for (int i = 1; i < arr.length; i++) { if(recognize(star, arr[i])) star = arr[i]; }
    return star;

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关算法题练习——JS Node+python题解BM19 寻找峰值

描述 > 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。 > > 1.峰值元素是指其值严格大于左右

落日映苍穹つ/ 2024年04月07日 16:03/ 0 赞/ 63 阅读

相关算法：二分法---寻找H指数

![在这里插入图片描述][3e8bd4338b5140bfae7afb4d9bb2f9bd.png] 1、题目：给你一个整数数组 `citations` ，

红太狼/ 2024年03月03日 03:12/ 0 赞/ 65 阅读

相关 webmin(web明星缩写)

Linux服务器下Webmin怎样安装配置？安装完成后，可以在本地或者远程浏览器上打开一个特定的端口来进入Webmin。通常是10000，这是安装时程序缺省提供的htt

逃离我推掉我的手/ 2023年09月26日 14:39/ 0 赞/ 7 阅读

相关算法面试题:寻找数组中重复的数字

题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了. 也不知

墨蓝/ 2023年07月09日 13:27/ 0 赞/ 16 阅读

相关算法题：寻找两个正序数组的中位数

算法题：寻找两个正序数组的中位数题目描述示例提示代码执行效率题目描述给定两个大小为 m 和 n 的正序（

蔚落/ 2022年12月27日 07:35/ 0 赞/ 122 阅读

相关 js算法--寻找峰值

解释峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums\[i\] ≠ nums\[i+1\]，找到峰值元素并返回其索引。数组可能包含多

柔光的暖阳◎/ 2022年12月22日 09:24/ 0 赞/ 151 阅读

相关字符串寻找字串暴力算法

在长字符串中查找子字符串，使用暴力算法，可以使用双指针，进行暴力破解 func BF(S string , T string) int{

矫情吗；*/ 2022年12月21日 03:15/ 0 赞/ 141 阅读

相关前端算法题--寻找两个正序数组中位数

寻找两个正序数组中位数 > 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。示例1：

刺骨的言语ヽ痛彻心扉/ 2022年09月03日 16:18/ 0 赞/ 216 阅读

相关寻找三角形（编程题）

三维空间中有N个点，每个点可能是三种颜色的其中之一，三种颜色分别是红绿蓝，分别用'R', 'G', 'B'表示。现在要找出三个点，并组成一个三角形，使得这

﹏ヽ暗。殇╰゛Y/ 2022年06月16日 00:29/ 0 赞/ 186 阅读

相关算法题 —— 寻找明星

前段时间在现场面试的时候碰到的题目，做下总结。题目设定 -------------------- 有 N 个人，其中有1个人是明星，其他 N-1 个人是群众，所

我会带着你远行/ 2022年05月24日 03:27/ 0 赞/ 132 阅读