一尘不染

O(nlogn)算法-在二进制字符串中找到三个均匀间隔的算法

algorithm

昨天我在算法测试中遇到了这个问题,但我找不到答案。这绝对让我发疯,因为它价值40分。我认为大多数班级都无法正确解决该问题,因为在过去的24小时内我没有提出解决方案。

给定任意一个长度为n的二进制字符串,请在该字符串中找到三个均等的字符串(如果存在)。编写一个算法,可以在O(n * log(n))时间内解决此问题。

因此,这样的字符串具有三个“等间距”的字符串:11100000,0100100100

编辑:这是一个随机数,因此它应该可以处理任何数字。我提供的示例旨在说明“均匀分布”的属性。因此1001011是有效数字。其中1、4和7是等距排列的。


阅读 228

收藏
2020-07-28

共1个答案

一尘不染

最后!跟进sdcvvc答案中的线索,我们得到了:问题的O(nlogn)算法!了解之后,它也很简单。那些认为FFT是正确的人。

问题是:给我们一个S长度为_n_的二进制字符串,我们想在其中找到三个均匀间隔的1。例如,S可能是110110010,其中 n =
9。它在位置2、5和8处平均间隔为1。

  1. S从左到右扫描,并列出L位置1。对于S=110110010上面的列表,我们有L = [1、2、4、5、8]。此步骤为O(n)。现在的问题是要找到一个 长度为3的算术级数L,即找到不同 的a,b,CL,使得 BA = CB ,或者等效 A + C = 2b中 。对于上面的示例,我们要查找进度(2、5、8)。

  2. 对于中的每个 k ,用项 x k 构成 多项式 。对于上面的示例,我们使多项式 p(x)=(x + x 2 + x 4 + x 5 + x 8 。此步骤为O(n)。p L __

  3. 使用快速傅立叶变换找到多项式q= p 2。对于上面的示例,我们得到多项式 q(x)= x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2此步骤为O(n log n)。* __ *

  4. 忽略与 x 2k_对应的所有项(对于in中的某些 _kL。对于上面的示例,我们得到的术语 X 16,3× 10,X 8,X 4,X 2。如果您选择完全这样做,则此步骤为O(n)。

这里的关键点:任何系数 X 2B_为 _bL精确 的对数 (A,C)L,使得 A + C = 2b中 。[CLRS,例如
[30.1-7]一对这样的对总是 (b,b) (因此系数至少为1),但是如果存在其他对 (a,c) ,那么该系数至少为 (a,c)的3。 )
(c,a) 。对于上面的示例,由于AP(2,5,8),我们的 _x 10_系数正好为3。(这些系数 _x
2b_由于上述原因,将始终为奇数。q中的所有其他系数将始终为偶数。)

因此,该算法将查看这些项 x 2b_的系数,并查看它们中的任何一个是否大于1。如果没有,则没有均匀间隔的1s。如果有 _是 一个 b
L为其中的系数 X 2b的_是大于1,则我们知道有一些对 (A,C) -比其它 (B,B) 对于其中- _A + C = 2b中
。要查找实际的对,我们只是尝试每 一个L(对应 ç2B-A ),看看是否有一个1在位置 2B-AS。此步骤为O(n)。

就是这样,伙计们。


有人可能会问:我们需要使用FFT吗?很多答案,如测试的,flybywire的,和RSP的,建议的做法是检查每对1S的,并认为如果有一个1在“第三”的位置,在O可能会工作(N log
n)的基础上,直觉如果1太多,我们将很容易找到三元组;如果1太少,则检查所有对都花费很少的时间。不幸的是,虽然这种直觉是正确的,简单的方法
优于为O(n
2),它是不是好显著。就像sdcvvc的答案一样,我们可以采用长度为 n = 3 k 的字符串的“类似Cantor的集合”,其中三元表示中只有0和2(无1)的位置为1。 这样的字符串中有 _2 k = n (log 2)/(log 3) ≈n0.63_个,并且没有均匀间隔的1s,因此检查所有对将是其中1s的平方的数量级: _4 ķ ≈ñ 1.26_不幸比渐近大得多(N logn)的。实际上,最坏的情况甚至更糟:1953年,LeoMoser构造(有效)了其中具有 _n 1-c
/√(log n)
1s但没有均匀间隔1的弦,这意味着在这样的弦上,简单该方法将花费 Θ(n 2-2c /√(log n))-只有一个
很小的
一点优于 Θ(N 2),令人惊讶!


长度为n的字符串中最大1的个数,没有3个均匀间隔的(我们在上面看到的至少是简单的Cantor型构造的 n为 0.63,而至少 n 1-c /√(log
n)_为Moser的结构)-这是OEIS
A003002
。也可以直接从OEIS
A065825
计算为k,以使A065825(k)≤n
<A065825(k + 1)。我写了一个程序来找到这些字符串,结果证明贪心算法 _不能
给出最长的字符串。例如,对于 n = 9,我们可以获得5
1s(110100011),但是对于 n ,贪婪只给出4(110110000) __= 26我们可以得到11
1(11001010001000010110001101),但是贪心只得到8(11011000011011000000000000),对于 n =
74我们可以得到22
1(11000010110001000001001011010001000000000000000010001011010000010001101000011),但是贪婪只得到16(11011000011011000000000000011011000011011000000000000000000000000000)。不过,他们确实在相当多的地方达成共识,直到50个(例如38个到50个)。如OEIS参考文献所述,Jaroslaw
Wroblewski似乎对此问题感兴趣,并且他在这些非平均集合上维护了一个网站。确切数字最多只能知道194。

2020-07-28