老婆给的解法: O(n) 判断函数 f(A, B) // return 1 means A know B, return 0 means A do not know B. 输入array代表n个人： A[n] // from 0 to n-1; int findCelebrity(vector<int> A) { int num = 0; for (int i = 1; i < A.size(); i++) { if (f(A[num], A)) { num = i; } } return num; }
加油，继续做下一题 Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element. We define an array is non-decreasing if nums <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2). Example 1: Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array. Example 2: Input: nums = [4,2,1] Output: false Explanation: You can't get a non-decreasing array by modify at most one element.
回复 49楼surezzz的帖子 It’s directed connected graph. The question is similar to finding the root of a tree, with additional requirement of not visiting the same node twice. So it is O(log n).
一屋子人在聚会， 有一个名人， 人人都认识他， 他不认识任何人， 别人之间可能认识也可能不认识, 假设会通过一个函数告诉你。 怎么把这个名人高效的找出来？
哈哈.
抓住一个伪码工。
奥数比这题要难一百倍至少。这个太简单了。
1.对于每个 i 属于 1...(n-1) ， 2. j 属于 I +1...,n If j 认识 i Remove j Break 循环 2 否则 Remove i Break循环 1
最后剩的就是要的人
不会编程序。但是中层管理也需要知道一点半点，免得被马工们忽悠
O(1)?
👍
我记得小学奥数就是这个款，你说什么阶段的奥数比这个难多了？
我看不懂那个题说啥，什么叫通过一个函数告诉你。可能是翻译辞不达意？建议楼主把原题完整贴出来吧
随便找个人开始, 每个已被找到过的人设个被找到过的标记. 根据函数提供的那个人认识的所有人里, 找到第一个还没被找到过的人. 继续循环找下一个人.
最后那个没有认识任何人的就是名人. O(N^2) with O(N) space.
老板, 可以给offer吗?
Strong no hire
😭
每次任选两个a,b, 如果 f(a,b) = 1 那么 a 不是名人 （名人不认识所有人） f(a,b) = 0 那么 b 不是名人 （所有人都认识名人） 所以每次调动函数都可以排除一个人。调动n-1次后就剩名人了
无论如何你都要遍历完所有人，怎么可能log？
这个答案是错的。因为没有prioritize a在f(a,b) = 0的情况。每次出现f(a,b) = 0都应该继续以f(a,x)查找
反之对 f(a,b)= 1 也应该prioritize b
每次取一对人， 1.互相认识，全丢掉 2.互相不认识，全丢掉 3.单向认识，留下一个 重复直到剩下一个 每次loop会筛掉至少一半的人，最坏情况每次筛掉一个，所以线性时间
没觉得这个答案有什么问题。出现f(a,b)=0没有任何理由prioritize f(a,x)，因为剩下的candidate里面机会均等，查f(c,d)甚至f(e,f)也没问题。
剩下candidate机会并不均等，posterior变了
拜托这个不是面试 我只想写个大家看得懂的答案
想要贡献的话就写个optimized solution 我继续黑五刷刷刷去了
O(1) 人人都认识的意思就啊哈，随便找个人问一下，“你是不是名人?如果不是那谁是?”不就行了？
从里面任选2个人出来， 看他们互相认识不认识，有4种可能情况，第一种情况，if 两个人都互相认识，则两个人都去掉，都不会是领导， 第二种情况，if 两个人都不互相认识，则两个人也不可能是领导，则两个人也都去掉， 第三种情况，如果a认识b，b不认识a，则a不可能是领导，b可能是领导，则a去掉，b留着，，第四种情况，跟第三种情况相反，则a留着，b去掉， 这时就只剩下n-1个人或者n-2个人，一个循环结束了，
接着又进行第二个循环。
直到最后一个循环，只剩下两个人了，x和y，如果x认识y，则y是领导，如果y认识x，则x是领导。
有道理，但之前答案也不能说是错的吧，时间复杂度不变，只是少点optimization
正解
如果是这个题的话，那比楼主原来的描述清楚多了。 关键条件是名人不认识任何人。如果去掉这个条件，那么假设5个人，假设认识函数形成下面的矩阵： X X X X O X X X O X X X O X X X O X X X X X X X X 只有一行一行的试。最差情况下，n平方
你这个是彻头彻尾错的解法。
简单举例， f(a, b), f(a,c)都排除a不是名人。
这个题目应该是O(n)的复杂度， 不过解法不是这样的
你咋还理解不了呢，第一个函数后，a就已经排除了，下一个函数不会再出现a了
int findCelebrity(vector<int> A) { int num = 0; for (int i = 1; i < A.size(); i++) { if (f(A[num], A)) { num = i; } } return num; }
给你个array： A[n] 你教教我怎么排除，怎么任意选a, b
c <- 1 for i in 2:n --- if f(c,i) ------ c <- i return c 这个是你太太的具体实现方法。这就是那个层主说的意思。但是还有其他具体的实现方法。比如从后面往前，而不是从前向后，或者先挑奇的序号，再挑偶的序号。那位层主把最关键的地方说明白了。
你不就照着我的写法写了一遍，
和之前说的排除算法完全无关
看我改过的回答
别扯了， 那个写法的思想根本不是挑两个a，b出来之前，一次排除一个。
你就是照着我代码一摸一样抄了一遍，这代码和你36楼自己的思想都完全不一样
#36 我的意思是说，如果少了一个条件，可以证明，没有比n平方更小的解答
加油，继续做下一题 Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element. We define an array is non-decreasing if nums <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Example 1: Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array. Example 2: Input: nums = [4,2,1] Output: false Explanation: You can't get a non-decreasing array by modify at most one element.
码农居然成为高工资行业，说明这个国家实业的确不行了。
正确答案就是O(log(n))，随机算法, walk on a directed graph。
It’s directed connected graph. The question is similar to finding the root of a tree, with additional requirement of not visiting the same node twice. So it is O(log n).
if (f(A[num], A)) { num = i; }
你写的这个，本质上不就是
如果 f(A[num], A) = 1, 排除 num 如果 f(A[num], A) = 0，排除 i
吗？ 跟之前那位层主的解法是一样的，就是任意选 a b 被修改成了按顺序选 a b 而已
见面一次可否让A和B都回答。这样省一半时间。