求一道简单题目的算法伪代码

发布网友发布时间：2022-04-24 23:25

共1个回答

热心网友时间：2023-10-14 11:18

可能的人k=第1人；
for（i=第二人;i不是最后一个人;i=下一个人)
{
if(k认识i==yes）
k=i
}

最后保留下来的一定是那个名人。
因为只有遇到名人，才能保证之后一定不会再碰见认识的人。
而在碰到名人之前，一定会遇到名人（假定你那随机之后一定有一个名人），
那么k就会指向名人。

有点像脑经急转弯。。
你的方法应该是两两相比较，然后比较结果再比较的算法吧。。追问

文字太多了，还是发图片吧。。。。

追答恩。你的解法就是我说的那种两两比较后，再把结果拿来比较。
我的直觉告诉我好像是nlog n的复杂度，符合T（N）=2T(n/2)+k的模型。
但你这么算也是对的，这算是O(n)的算法。
但是你n的系数比我的大，而且应该还有很多数据交换。
其实完全可以向我那样只向一个方向问，那么你的最后询问次数也是n，而不是2n。

我还谈不上大神。。。不过确实晚上做事效率高些。
干扰少点，可以安心写代码~