这是我的任务:
存在一个有 n 个整数的循环有序链表。每个元素都有一个指向下一个更大项目的后继指针。列表中最大的项目指向最小的项目。确定传入的目标项是否是列表的成员。您可以通过两种方式访问列表中的项目:您可以跟随已访问项目的下一个指针,或者可以使用函数“RAND”,该函数返回指向列表中均匀随机项目的指针。创建一个随机算法,找到目标项,最多进行 O(√n) 次期望传递,并始终返回正确的答案。
我不确定如何以所需的时间复杂度构建算法。我认为这与计算和存储列表中的一些总和有关,但无法弄清楚这一步。
最佳答案
解决方案基于戴夫的评论:
Use RAND
sqrt(n)
times, storing the largest element < target. Show that this is expected to be withinsqrt(n)
of the target.
用i
表示列表中小于目标元素的最大元素的索引。
现在让我们计算在 sqrt(n)
试验中击中 (i - sqrt(n), i]
范围内的元素的期望。在每次试验中,概率命中范围是范围长度除以列表长度,即 sqrt(n)/n = 1/sqrt(n)
,所以
E = 1/sqrt(n) * sqrt(n) = 1.
因此,我们希望通过在 sqrt(n)
试验中选择小于目标的最大元素来检查目标元素是否存在,然后线性推进 sqrt(n)
项目。
关于math - 有序循环链表中随机整数的存在性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49786982/