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

小开

你可以改编 Rabin-Karp 算法。它的复杂度是0(n) ，所以它可以帮助你。

看看 http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

小开

我怀疑一个看起来像 O (n ^ 2)的简单方法实际上会产生更好的结果，比如 O (n ln (n))。测试时间最长的序列(对于任何给定的 n)是那些不包含三元组的序列，并且对序列中可以包含的1的数目有严格的限制。

我已经想出了一些有力的论据，但是我还没有找到一个完整的证据。我要在黑暗中尝试一下: 答案是一个非常聪明的想法，教授已经知道了这么长时间，它似乎是显而易见的，但这对学生来说太难了。(要么是这样，要么是你在讲课时睡过头了。)

小开

这似乎是一个有趣的问题，所以我决定尝试一下。

我的假设是，111000001将找到前三个和成功。本质上，1后面的0的数量是很重要的，因为根据你的定义，0111000和111000是一样的。一旦你找到两个1的例子，下一个1就完成了三部曲。

下面是 Python 语言:

def find_three(bstring):
print bstring
dict = {}
lastone = -1
zerocount = 0
for i in range(len(bstring)):
if bstring[i] == '1':
print i, ': 1'
if lastone != -1:
if(zerocount in dict):
dict[zerocount].append(lastone)
if len(dict[zerocount]) == 2:
dict[zerocount].append(i)
return True, dict
else:
dict[zerocount] = [lastone]
lastone = i
zerocount = 0
else:
zerocount = zerocount + 1
#this is really just book keeping, as we have failed at this point
if lastone != -1:
if(zerocount in dict):
dict[zerocount].append(lastone)
else:
dict[zerocount] = [lastone]
return False, dict

这是第一次尝试，所以我相信这可以写得更干净。请在下面列出此方法失败的情况。

小开

还没能想出解决办法: (，但有一些想法。)。

如果我们从一个相反的问题开始: 构造一个最大值为1且没有任何均匀间隔的三元组的序列会怎样。如果你能证明1的最大个数是 o (n) ，那么你就可以通过只迭代1的列表来改进你的估计。

小开

对于简单的问题类型(例如，你在它之间搜索三个“1”只有(即0或以上)「0」) ，它非常简单: 你可以在每个“1”分割序列，并寻找两个相邻的子序列具有相同的长度(第二个子序列当然不是最后一个)。显然，这可以在 O (n)时间内完成。

对于更复杂的版本(例如，你搜索一个索引我和一个间隙克 > 0使得 s[i]==s[i+g]==s[i+2*g]=="1") ，我不确定是否存在一个 O (n log n)解决方案，因为可能有 O (n2)三联体具有这种性质(想一想所有的字符串，大约有 N2/2这样的三联体)。当然，你只是在寻找其中的一个，但我目前还不知道，如何找到它..。

小开

这能解决问题吗？I’，不确定它是否是 O (nlogn) ，但是在我看来它比 O (n2)好，因为唯一不能找到三元组的方法就是素数分布。

还有改进的余地，第二个发现的1可能是下一个第一个1。也没有错误检查。

#include <iostream>


#include <string>


int findIt(std::string toCheck) {
for (int i=0; i<toCheck.length(); i++) {
if (toCheck[i]=='1') {
std::cout << i << ": " << toCheck[i];
for (int j = i+1; j<toCheck.length(); j++) {
if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << "    found" << std::endl;
return 0;
}
}
}
}
return -1;
}


int main (int agrc, char* args[]) {
std::string toCheck("1001011");
findIt(toCheck);
std::cin.get();
return 0;
}

小开

进入这个问题的一个途径是考虑因素和转变。

通过移位，您可以将一串1和0与移位后的版本进行比较。然后你拿一样的。举个例子:

1010101010
1010101010
------------
001010101000

得到的1(按位 AND)必须表示所有那些1之间的间距均匀为2的1。同样的例子又变了三个:

1010101010
1010101010
-------------
0000000000000

在这种情况下，没有1是均匀间隔的3。

这说明了什么？你只需要测试质数的移位。例如，假设你有两个1，它们之间相隔六个。你只需要测试“两个”班次和“三个”班次(因为这些除以六)。例如:

10000010
10000010 (Shift by two)
10000010
10000010 (We have a match)


10000010
10000010 (Shift by three)
10000010 (We have a match)

所以你唯一需要检查的变化是2,3,5,7,11,13等等。直到最接近数字字符串大小的平方根的素数。

快破案了？

我想我离解决方案更近了，基本上:

扫描字符串寻找1。对于每个1音符，它是取其位置的模后的余数。模数范围从1到字符串大小的一半。这是因为最大可能的分离大小是字符串的一半。这是在 O (n ^ 2)中完成的。但是。只有素模需要检查，所以 O (n ^ 2/log (n))
首先将模/余数列表按最大模的顺序排序，这可以在 O (n * log (n))时间内完成。
寻找三个相同的连续模量/余数。
想办法找回他们的位置！

我认为答案的最大线索，就是最快的排序算法，是 O (n * log (n))。

错

正如一位同事指出的那样，第一步是错误的。如果我们在位置2,12和102有1。然后取10的模，它们都有相同的余数，但是它们之间的距离不是相等的！对不起。

小开

这是可以在线性时间 O (n)内求解的

从头开始，等待第一个1
开始数零。
当您点击1存储数量的计数零(有效数字也是0) 数字零-> 普雷维零
开始数零。
当您点击1时，检查 NumberOfZeros = = PreverZeros

如果是真的

Else 数字零-> 前置零 and goto 4

小开

一个有趣的问题，但是一旦你意识到两个’1’之间的实际模式并不重要，算法就会变成:

扫描寻找“1”
从下一个位置开始扫描另一个“1”(到数组的末尾减去与当前第一个“1”的距离，否则第三个“1”将超出界限)
如果在第二个“1”的位置加上到第一个“1”的距离，找到第三个“1”，我们就得到了均匀的空间。

在代码中，以 JTest 的方式，(注意这段代码并不是为了最高效而编写的，我添加了一些 println 来查看会发生什么。)

import java.util.Random;


import junit.framework.TestCase;


public class AlgorithmTest extends TestCase {


/**
* Constructor for GetNumberTest.
*
* @param name The test's name.
*/
public AlgorithmTest(String name) {
super(name);
}


/**
* @see TestCase#setUp()
*/
protected void setUp() throws Exception {
super.setUp();
}


/**
* @see TestCase#tearDown()
*/
protected void tearDown() throws Exception {
super.tearDown();
}


/**
* Tests the algorithm.
*/
public void testEvenlySpacedOnes() {


assertFalse(isEvenlySpaced(1));
assertFalse(isEvenlySpaced(0x058003));
assertTrue(isEvenlySpaced(0x07001));
assertTrue(isEvenlySpaced(0x01007));
assertTrue(isEvenlySpaced(0x101010));


// some fun tests
Random random = new Random();


isEvenlySpaced(random.nextLong());
isEvenlySpaced(random.nextLong());
isEvenlySpaced(random.nextLong());
}


/**
* @param testBits
*/
private boolean isEvenlySpaced(long testBits) {
String testString = Long.toBinaryString(testBits);
char[] ones = testString.toCharArray();
final char ONE = '1';


for (int n = 0; n < ones.length - 1; n++) {


if (ONE == ones[n]) {
for (int m = n + 1; m < ones.length - m + n; m++) {


if (ONE == ones[m] && ONE == ones[m + m - n]) {
System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
System.out.println("               at: " + n + ", " + m + ", " + (m + m - n));
return true;
}
}
}
}


System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
return false;
}
}

小开

我假设这是 nlog (n)的原因是由于以下原因:

要找到作为三元组开始的1，需要检查(n-2)字符。如果到那时还没有找到它，那么就不会找到(字符 n-1和 n 不能开始一个三元组) (O (n))
为了找到第二个1是三元组的一部分(由第一个开始) ，需要检查 m/2(m = n-x，其中 x 是前一个1的偏移量)字符。这是因为，如果你还没有找到第二个1当你从第一个到最后的一半的时候，你不会找到，因为第三个1必须和第二个1完全一样的距离。(O (log (n)))
它 O (1)查找最后一个1，因为您知道索引，它必须在您找到第一个和第二个索引的时候。

所以，有 n，log (n)和1... O (nlogn)

编辑: 哎呀，我的错。我的大脑设置 n/2是 logn... ... 显然不是(项目数量加倍仍然是内部循环迭代次数的两倍)。这仍然是 n ^ 2，不能解决这个问题。好吧，至少我得写点代码:)

在 Tcl 中的实现

proc get-triplet {input} {
for {set first 0} {$first < [string length $input]-2} {incr first} {
if {[string index $input $first] != 1} {
continue
}
set start [expr {$first + 1}]
set end [expr {1+ $first + (([string length $input] - $first) /2)}]
for {set second $start} {$second < $end} {incr second} {
if {[string index $input $second] != 1} {
continue
}
set last [expr {($second - $first) + $second}]
if {[string index $input $last] == 1} {
return [list $first $second $last]
}
}
}
return {}
}


get-triplet 10101      ;# 0 2 4
get-triplet 10111      ;# 0 2 4
get-triplet 11100000   ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7

小开

我想到了一个分而治之的办法，也许可行。

首先，在预处理中，你需要将所有小于输入大小一半的数字(N/3)插入到一个列表中。

给定一个字符串: 0000010101000100(注意，这个示例是有效的)

将从1到(16/2)的所有素数(和1)插入列表: {1,2,3,4,5,6,7}

然后把它一分为二:

100000101 01000100

继续这样做，直到得到大小为1的字符串。对于所有大小为1的字符串，将该字符串的索引添加到可能性列表中; 否则，如果失败，返回 -1。

您还需要返回与每个起始索引相关的仍然可能的间隔距离列表。(从上面的列表开始，移除数字)在这里，一个空列表意味着你只处理一个1，所以在这一点上任何间距都是可能的; 否则列表包括必须排除的间距。

因此，我们继续上面的例子:

1000 0101 0100 0100

10 00 01 01 01 00 01 00

1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0

在第一个合并步骤中，我们现在有八组两个。在第一个例子中，我们有一个集合的可能性，但是我们知道1的间隔是不可能的，因为另一个零在那里。所以我们返回0(对于索引)和{2,3,4,5,7} ，因为间隔为1是不可能的。在第二种情况下，我们什么都没有，因此返回 -1。在第三个索引中，我们有一个匹配，索引5中没有消除间距，因此返回5，{1,2,3,4,5,7}。在第四对中，我们返回7，{1,2,3,4,5,7}。在第五个中，返回9，{1,2,3,4,5,7}。在第六个，返回 -1。在第七个中，返回13，{1,2,3,4,5,7}。第八局，返回 -1。

再合并成四组四，我们有:

返回值(0，{4,5,6,7}) 0101: 返回(5，{2,3,4,5,6,7}) ，(7，{1,2,3,4,5,6,7}) 返回值(9，{3,4,5,6,7}) 返回值(13，{3,4,5,6,7})

分为八组:

10000101: 返回(0，{5,7}) ，(5，{2,3,4,5,6,7}) ，(7，{1,2,3,4,5,6,7}) 返回值(9，{4,7}) ，(13，{3,4,5,6,7})

结合成一组16个:

10000101 01000100

随着我们的进展，我们一直在检查所有的可能性。到这一步，我们已经留下了超出字符串末尾的内容，但现在我们可以检查所有的可能性。

基本上，我们用5和7的间距检查第一个1，发现它们没有与1对齐。(注意，每个检查是 CONSTANT，而不是线性时间)然后我们检查第二个(索引5) ，其间距为2、3、4、5、6和7——或者我们会这样做，但是我们可以在2处停止，因为这实际上是匹配的。

这算法可真长。

我不知道这是否是100% 的 O (n log n)，因为最后一步，但一切到那里肯定是 O (n log n)，就我所知。我稍后将回到这个问题，并试图完善最后一步。

编辑: 改变我的回答，以反映韦尔伯格的评论。对不起，我错了。稍后我也会写一些伪代码，这样我就有更多的时间来解释我写的东西了。;-)

小开

我想我已经找到了解决这个问题的方法，但是我不能构造一个正式的证明。我创建的解决方案是用 Java 编写的，它使用计数器 n 来计算它执行了多少列表/数组访问。所以如果 n 是正确的，它应该小于或等于 stringLlength * log (stringLlength)。我试过数字0到2 ^ 22，它成功了。

它首先迭代输入字符串，并列出所有包含1的索引。这只是 O (n)。

然后从索引列表中选择 firstIndex 和大于第一个的 Second Index。这两个索引必须包含一个，因为它们在索引列表中。从那里可以计算出第三个索引。如果 inputString [ Third Index ]是1，那么它将停止。

public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;


//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
if(input.charAt(i)=='1'){
ones.add(i);
}
}


//If less than three ones in list, just stop
if(ones.size()<3){
return n;
}


int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
n++;
firstIndex = ones.get(x);


for(int y=x+1; y<ones.size()-1; y++){
n++;
secondIndex = ones.get(y);
thirdIndex = secondIndex*2 - firstIndex;


if(thirdIndex >= input.length()){
break;
}


n++;
if(input.charAt(thirdIndex) == '1'){
//This case is satisfied if it has found three evenly spaced ones
//System.out.println("This one => " + input);
return n;
}
}
}


return n;

}

附加说明: 计数器 n 在迭代输入字符串以构造索引列表时不会递增。这个操作是 O (n) ，因此它不会对算法的复杂度产生任何影响。

小开

这不是一个解决方案，而是一个类似于奥莱克西在想的思路

我一直在尝试创建一个数字最大的序列，它们都很有趣，我得到了125个数字，这里是它通过尝试插入尽可能多的“1”位找到的前3个数字:

11011000011011000000000000000000000000110110000000000000000000000000000000000000000001101100000000000000000000011011000000000000000000000000001101100000000000000000000011011000000000000
10110100010110100000000000000000001011010100000000000000000000000000000000000000000000000001011010100000000000000000000101101010000000000000000000000000000001010101010000000000000000000
10011001001100110010010010010000000000000000100110010000000000000001001100100000000000100110010000000000001001100100100100100100000000000000000000000000001100000000000000000000000000000

注意，它们都是分形(考虑到约束，这并不奇怪)。也许在反向思考的过程中会有一些东西，也许如果字符串不是具有特征的分形，那么它一定有一个重复的模式？

感谢贝塔系统提供了更好的术语来描述这些数字。

更新: 遗憾的是，当以一个足够大的初始字符串开始时，这种模式看起来会崩溃，比如: 10000000000001:

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001

小开

在这里，我将给出我的粗略猜测，让那些更擅长计算复杂度的人来帮助我了解我的算法在 O 符号方面的表现

给定二进制字符串0000101000100(例如)
0的头部和尾部-> 00000101000100
我们从前面的计算中得到101010001
检查中间位是否为“ one”，如果为真，则找到有效的三个均匀间隔的“ one”(只有当位数为奇数时)
相对地，如果剩余的裁剪位数是偶数，则头部和尾部的“ one”不能是均匀间隔的“ one”的一部分,
我们使用1010100001作为例子(与一个额外的“零”成为偶数作物) ，在这种情况下，我们需要再次作物，然后成为-> 1010100001
我们从前面的计算中得到10101，然后检查中间位，我们又找到了均匀间隔的位

我不知道怎么计算这个的复杂度，有人能帮忙吗？

添加一些代码来说明我的想法

编辑2: 尝试编译我的代码，发现一些重大错误，修复

char *binaryStr = "0000010101000100";


int main() {
int head, tail, pos;
head = 0;
tail = strlen(binaryStr)-1;
if( (pos = find3even(head, tail)) >=0 )
printf("found it at position %d\n", pos);
return 0;
}


int find3even(int head, int tail) {
int pos = 0;
if(head >= tail) return -1;
while(binaryStr[head] == '0')
if(head<tail) head++;
while(binaryStr[tail] == '0')
if(head<tail) tail--;
if(head >= tail) return -1;
if( (tail-head)%2 == 0 && //true if odd numbered
(binaryStr[head + (tail-head)/2] == '1') ) {
return head;
}else {
if( (pos = find3even(head, tail-1)) >=0 )
return pos;
if( (pos = find3even(head+1, tail)) >=0 )
return pos;
}
return -1;
}

小开

我认为这个算法具有 O (n logn)复杂度(C + + ，DevStudio 2k5)。现在，我不知道如何分析算法来确定其复杂性的细节，所以我在代码中添加了一些度量收集信息。该代码计算任何给定输入的1和0的序列上完成的测试的数量(希望，我没有做出一个球的算法)。我们可以根据 O 值比较测试的实际数量，看看是否存在相关性。

#include <iostream>
using namespace std;


bool HasEvenBits (string &sequence, int &num_compares)
{
bool
has_even_bits = false;


num_compares = 0;


for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
{
for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
{
++num_compares;
if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
{
has_even_bits = true;
// we could 'break' here, but I want to know the worst case scenario so keep going to the end
}
}
}


return has_even_bits;
}


int main ()
{
int
count;


string
input = "111";


for (int i = 3 ; i < 32 ; ++i)
{
HasEvenBits (input, count);
cout << i << ", " << count << endl;
input += "0";
}
}

该程序输出每个字符串长度不超过32个字符的测试次数:

 n  Tests  n log (n)
=====================
3     1     1.43
4     2     2.41
5     4     3.49
6     6     4.67
7     9     5.92
8    12     7.22
9    16     8.59
10    20    10.00
11    25    11.46
12    30    12.95
13    36    14.48
14    42    16.05
15    49    17.64
16    56    19.27
17    64    20.92
18    72    22.59
19    81    24.30
20    90    26.02
21   100    27.77
22   110    29.53
23   121    31.32
24   132    33.13
25   144    34.95
26   156    36.79
27   169    38.65
28   182    40.52
29   196    42.41
30   210    44.31
31   225    46.23

我还添加了’n log n’值。使用您选择的绘图工具绘制这些图表，以查看两个结果之间的相关性。这个分析是否扩展到 n 的所有值？我不知道。

小开

我想出了这样的主意:

def IsSymetric(number):
number = number.strip('0')


if len(number) < 3:
return False
if len(number) % 2 == 0:
return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
else:
if number[len(number)//2] == '1':
return True
return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
return False

这个灵感来自于 andycjw。

把0删掉。
如果甚至那么测试两个子字符串0-(len-2)(跳过最后一个字符)和从1-(len-1)(跳过第一个字符)
如果没有比如果中间的字符是一个，那么我们就成功了。否则，将字符串在中间分开，不包含中间元素，并检查两个部分。

至于复杂度，这可能是 O (nlogn) ，因为在每个递归中，我们要除以2。

希望能有帮助。

小开

这可能会有帮助。

这个问题可归结为:

给定一个正整数序列，找到一个分为前缀和后缀的连续子序列，使得子序列前缀的和等于子序列后缀的和。

例如，给定一个 [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ]序列，我们将发现一个前缀为 [ 3, 6 ]的 [ 3, 6, 5, 2, 2]的子序列，前缀和为 9，后缀和为 9的 [ 5, 2, 2 ]的后缀。

减少额如下:

给定一个由0和1组成的序列，从最左边的1开始，继续向右移动。每次遇到另一个，记录自遇到前一个以来的移动次数，并将该数字附加到结果序列。

例如，给定一个 [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ]序列，我们会发现 [ 1, 3, 4]的减少。从这个还原，我们计算了 [ 1, 3, 4]的连续子序列，[ 1, 3]的前缀与 4的总和，以及 [ 4 ]的后缀与 4的总和。

这种减少可以在 O(n)中计算出来。

不幸的是，我不知道接下来该怎么办。

小开

假设:

只是错误的，讨论 log (n)数的上限

编辑:

现在我发现使用康托数(如果正确) ，集合上的密度是(2/3) ^ Log _ 3(n)(多么奇怪的函数) ，我同意，Log (n)/n 密度非常强。

如果这是上限，那么有一个算法可以在至少 O (n * (3/2) ^ (log (n)/log (3)))时间复杂度和 O (3/2) ^ (log (n)/log (3))空间复杂度下解决这个问题。(检查司法部的算法)

这仍然比 O (n ^ 2)要好得多

这个函数((3/2) ^ (log (n)/log (3)))乍一看像 n * log (n)。

我是怎么得到这个配方的？

在线上应用康托尔数字。
假设字符串的长度为3 ^ p = = n
在生成 Cantor 字符串的每个步骤中，保留以前的1的2/3。

这意味着(n * ((2/3) ^ p))-> (((3 ^ p)) * ((2/3) ^ p))剩余的1和简化后的2 ^ p。这意味着2 ^ p 在3 ^ p string-> (3/2) ^ p ones 中
((3/2) ^ (log (n)/log (3)))

小开

扫描1时，将它们的位置添加到 List 中。当添加第二个和连续的1时，将它们与目前为止列表中的每个位置进行比较。间距等于 currentOne (中间)-previousOne (左)。右边的位是 currentOne + space。如果是1，结束。

一个列表与它们之间的空间成反比。简单地说，如果你在1之间有很多0(在最糟糕的情况下) ，你已知的1的列表会增长得很慢。

using System;
using System.Collections.Generic;


namespace spacedOnes
{
class Program
{
static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};


static void Main(string[] args)
{
var bytes = new byte[4];
var r = new Random();
r.NextBytes(bytes);
foreach (var b in bytes) {
Console.Write(getByteString(b));
}
Console.WriteLine();
var bitCount = bytes.Length * 8;
var done = false;
var onePositions = new List<int>();
for (var i = 0; i < bitCount; i++)
{
if (isOne(bytes, i)) {
if (onePositions.Count > 0) {
foreach (var knownOne in onePositions) {
var spacing = i - knownOne;
var k = i + spacing;
if (k < bitCount && isOne(bytes, k)) {
Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
done = true;
break;
}
}
}
if (done) {
break;
}
onePositions.Add(i);
}
}
Console.ReadKey();
}


static String getByteString(byte b) {
var s = new char[8];
for (var i=0; i<s.Length; i++) {
s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
}
return new String(s);
}


static bool isOne(byte[] bytes, int i)
{
var byteIndex = i / 8;
var bitIndex = i % 8;
return (bytes[byteIndex] & _bits[bitIndex]) > 0;
}
}
}

小开

这里有一些想法，尽管我尽了最大的努力，似乎不会包装自己在一个弓。不过，它们可能是某人分析的一个有用的起点。

考虑下面提出的解决方案，这是一些人建议的方法，包括我自己在这个答案的前一个版本中。:)

修剪前后零。
扫描字符串寻找1。
当找到1时:
1. 假设它是解的中间1。
2. 对于前面的每个1，使用它保存的位置来计算最后的1的预期位置。
3. 如果计算的位置在字符串结尾之后，则它不能成为解决方案的一部分，因此将该位置从候选者列表中删除。
4. 检查溶液。
如果未找到解决方案，请将当前的1添加到候选人列表中。
重复，直到找不到更多的1。

现在考虑下面这样的输入字符串，它没有解决方案:

101
101001
1010010001
101001000100001
101001000100001000001

一般来说，这是形式为 j 0的 k 个字符串的串联，之后是从0到 k-1的 j 的1个字符串。

k=2  101
k=3  101001
k=4  1010010001
k=5  101001000100001
k=6  101001000100001000001

注意，子字符串的长度是1、2、3等等。所以，问题大小 n 有长度为1到 k 的子串，使得 n = k (k + 1)/2。

k=2  n= 3  101
k=3  n= 6  101001
k=4  n=10  1010010001
k=5  n=15  101001000100001
k=6  n=21  101001000100001000001

注意，k 还跟踪我们必须考虑的1的数目。请记住，每次我们看到一个1，我们需要考虑到目前为止看到的所有1。所以当我们看到第二个1时，我们只考虑第一个，当我们看到第三个1时，我们重新考虑前两个，当我们看到第四个1时，我们需要重新考虑前三个，以此类推。在算法的最后，我们考虑了 k (k-1)/2对1。叫 P。

k=2  n= 3  p= 1  101
k=3  n= 6  p= 3  101001
k=4  n=10  p= 6  1010010001
k=5  n=15  p=10  101001000100001
k=6  n=21  p=15  101001000100001000001

N 和 p 之间的关系是 n = p + k。

通过字符串的过程需要 O (n)时间。每次遇到1时，都会进行最多的(k-1)比较。因为 n = k (k + 1)/2，n > k * * 2，所以 sqrt (n) > k。这就是 O (n sqrt (n))或 O (n * * 3/2)。但是请注意，这可能不是一个真正的紧界限，因为比较的数量从1到最大值 k，它并不是 k 的全部时间。但我不知道怎么用数学来解释。

它仍然不是 O (n log (n))。此外，我无法证明这些输入是最糟糕的情况，尽管我怀疑它们是。我认为一个密集的包装1的前面的结果在一个更稀疏的包装结束。

由于某些人可能仍然觉得它有用，下面是我在 Perl 中的解决方案代码:

#!/usr/bin/perl


# read input as first argument
my $s = $ARGV[0];


# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";


# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;


# prime the position list with the first '1' at position 0
my @p = (0);


# start at position 1, which is the second character
my $i = 1;


print "the string is $s\n\n";


while ($i < length($s)) {
if (substr($s, $i, 1) eq '1') {
print "found '1' at position $i\n";
my @t = ();
# assuming this is the middle '1', go through the positions
# of all the prior '1's and check whether there's another '1'
# in the correct position after this '1' to make a solution
while (scalar @p) {
# $p is the position of the prior '1'
my $p = shift @p;
# $j is the corresponding position for the following '1'
my $j = 2 * $i - $p;
# if $j is off the end of the string then we don't need to
# check $p anymore
next if ($j >= length($s));
print "checking positions $p, $i, $j\n";
if (substr($s, $j, 1) eq '1') {
print "\nsolution found at positions $p, $i, $j\n";
exit 0;
}
# if $j isn't off the end of the string, keep $p for next time
push @t, $p;
}
@p = @t;
# add this '1' to the list of '1' positions
push @p, $i;
}
$i++;
}


print "\nno solution found\n";

小开

你的问题在这张纸(1999)中被称为“平均值”:

一个问题是3SUM-hard，如果问题3SUM 有一个次二次约简: 给定一组 n 个整数 A，A 中是否有元素 a，b，c 使得 a + b + c = 0？目前还不知道平均值是否为3SUM-hard。然而，从 AVERAGE 到3SUM 有一个简单的线性时间缩减，我们忽略了它的描述。

维基百科:

当整数在[-u... u ]范围内时，通过将 S 表示为位向量并使用 FFT 进行卷积，可以在时间 O (n + u lg u)内求出3SUM。

这足以解决你的问题:)。

非常的重要之处在于，O (n log n)的复杂性在于0和1的数量，而不是1的计数(可以作为数组给出，比如[1,5,9,15])。检查一个集合是否有一个等差数列，1的条件，是很困难的，根据那篇论文，到1999年为止，没有比 o (n²)更快的算法是已知的，并且推测它不存在。没有考虑到这一点的每个人都试图解决一个公开的问题。

其他有趣的信息，大多与本案无关:

下限:

一个简单的下界是类 Cantor 集(数字1)。. 3 ^ n-1在三元展开式中不含1-其密度为 n ^ (log _ 32)(大约0.631)。因此，如果集合不太大，那么任何检查，然后检查所有对，都不足以得到 O (n log n)。你得更聪明地研究序列。更好的下限是引用给你-它是 n^{1-c/(log (n)) ^ (1/2)}。这意味着康托集是没有最优的。

上限，我的老算法:

众所周知，对于大 n，不包含等差数列的{1,2，... ，n }的子集最多只有 n/(log n) ^ (1/20)个元素。论文在三等差数列里进一步证明: 该集合不能包含超过 n * 2²⁸ * (log log n/log n) ^1/2元素。因此，您可以检查是否实现了这个界限，如果没有，则检查对。这是 O (n² * log log n/log n)算法，比 O (n²)快。不幸的是，“关于三...”是在斯普林格-但第一页可用，本格林的解释是可用的给你，第28页，定理24。

顺便说一下，这些论文是1999年的——和我提到的第一篇论文是同一年的，所以这可能就是为什么第一篇没有提到这个结果的原因。

小开

好吧，我再试一下这个问题。我想我可以证明一个 O (n log (n))算法，它类似于那些已经讨论过的使用平衡二叉搜索树来存储1之间的距离的算法。这种方法的灵感来自于 Justice 关于将问题减少到1之间的距离列表的观察。

我们是否可以扫描输入字符串，在1的位置周围构造一个平衡二叉搜索树，使每个节点存储1的位置，并且每条边标记出每个子节点到相邻1的距离。例如:

10010001 gives the following tree


3
/ \
2 /   \ 3
/     \
0       7

这可以在 O (n log (n))中完成，因为对于大小为 n 的字符串，在最坏的情况下，每次插入都需要 O (log (n))。

然后，问题是搜索树，以发现在任何节点上，是否存在从该节点通过左子节点的路径，该路径的距离与通过右子节点的路径的距离相同。这可以在每个子树上递归地完成。在搜索中合并两个子树时，我们必须比较左边子树中路径的距离和右边子树中路径的距离。由于子树中的路径数与 log (n)成正比，节点数为 n，我相信这可以在 O (n log (n))时间内完成。

我错过什么了吗？

小开

修订: 2009-10-1723:00

我已经在大数字(比如2000万个字符串)上运行过这个算法，现在我相信这个算法不是 O (n logn)。尽管如此，它仍然是一个非常酷的实现，并且包含了许多优化，使它运行得非常快。它在25秒内计算24位或更少位的二进制字符串的所有排列。

我已经更新了代码以包括今天早些时候的 0 <= L < M < U <= X-1观测结果。

原创的

这在概念上类似于我回答的另一个问题。该代码还查看了一个系列中的三个值，并确定一个三元组是否满足一个条件。下面的 C # 代码就是根据这个改编的:

using System;
using System.Collections.Generic;


namespace StackOverflow1560523
{
class Program
{
public struct Pair<T>
{
public T Low, High;
}
static bool FindCandidate(int candidate,
List<int> arr,
List<int> pool,
Pair<int> pair,
ref int iterations)
{
int lower = pair.Low, upper = pair.High;
while ((lower >= 0) && (upper < pool.Count))
{
int lowRange = candidate - arr[pool[lower]];
int highRange = arr[pool[upper]] - candidate;
iterations++;
if (lowRange < highRange)
lower -= 1;
else if (lowRange > highRange)
upper += 1;
else
return true;
}
return false;
}
static List<int> BuildOnesArray(string s)
{
List<int> arr = new List<int>();
for (int i = 0; i < s.Length; i++)
if (s[i] == '1')
arr.Add(i);
return arr;
}
static void BuildIndexes(List<int> arr,
ref List<int> even, ref List<int> odd,
ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
{
for (int i = 0; i < arr.Count; i++)
{
bool isEven = (arr[i] & 1) == 0;
if (isEven)
{
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
even.Add(i);
}
else
{
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
odd.Add(i);
}
}
}


static int FindSpacedOnes(string s)
{
// List of indexes of 1s in the string
List<int> arr = BuildOnesArray(s);
//if (s.Length < 3)
//    return 0;


//  List of indexes to odd indexes in arr
List<int> odd = new List<int>(), even = new List<int>();


//  evenIndex has indexes into arr to bracket even numbers
//  oddIndex has indexes into arr to bracket odd numbers
List<Pair<int>> evenIndex = new List<Pair<int>>(),
oddIndex = new List<Pair<int>>();
BuildIndexes(arr,
ref even, ref odd,
ref evenIndex, ref oddIndex);


int iterations = 0;
for (int i = 1; i < arr.Count-1; i++)
{
int target = arr[i];
bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) ||
FindCandidate(target, arr, even, evenIndex[i], ref iterations);
if (found)
return iterations;
}
return iterations;
}
static IEnumerable<string> PowerSet(int n)
{
for (long i = (1L << (n-1)); i < (1L << n); i++)
{
yield return Convert.ToString(i, 2).PadLeft(n, '0');
}
}
static void Main(string[] args)
{
for (int i = 5; i < 64; i++)
{
int c = 0;
string hardest_string = "";
foreach (string s in PowerSet(i))
{
int cost = find_spaced_ones(s);
if (cost > c)
{
hardest_string = s;
c = cost;
Console.Write("{0} {1} {2}\r", i, c, hardest_string);
}
}
Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
}
}
}
}

主要区别是:

解的穷举搜索
这段代码生成一组数据，找出该算法最难解决的输入。
所有解决方案与最难解决方案
前一个问题的代码使用一个 python 生成器生成了所有解决方案。这段代码只显示每个模式长度中最难的部分。
计分算法
这段代码检查从中间元素到它的左边缘和右边缘的距离。Python 代码测试一个和是大于还是小于0。
在候选人身上集中
当前代码从中间到边缘查找候选者。前一个问题中的代码从边缘向中间运行。最后一个更改给出了很大的性能改进。
偶数池和奇数池的使用
基于本文最后的观察，代码搜索奇数对的偶数对，以找到 L 和 U，保持 M 不变。这减少了通过预计算信息进行搜索的次数。因此，该代码在 FindCandidate 的主循环中使用了两个间接级别，并要求对每个中间元素调用两次 FindCandidate: 对偶数调用一次，对奇数调用一次。

总体思路是处理索引，而不是数据的原始表示。计算出现1的数组允许算法在与数据中1的数量成正比的时间内运行，而不是在与数据长度成正比的时间内运行。这是一个标准的转换: 创建一个数据结构，允许更快的操作，同时保持问题等效。

结果已过期: 删除。

编辑: 2009-10-1618:48

在 yx 的数据中，其他的反应被认为是可以计算的硬数据的代表，我得到了这些结果... 我删除了这些。它们已经过时了。

我要指出的是，这些数据对我的算法来说并不是最难的，所以我认为 yx 分形是最难解决的假设是错误的。我认为，特定算法的最坏情况将取决于算法本身，而且不太可能在不同算法之间保持一致。

编辑: 2009-10-1713:30

进一步的观察。

首先，将0和1的字符串转换为1的每个位置的索引数组。假设数组 A 的长度是 X。那么目标就是找到

0 <= L < M < U <= X-1

这样

A[M] - A[L] = A[U] - A[M]

或者

2*A[M] = A[L] + A[U]

由于 A [ L ]和 A [ U ]和为偶数，它们不能是(偶数，奇数)或(奇数，偶数)。通过将 A []分成奇数和偶数两个池，并依次在奇数和偶数候选池中搜索 A [ M ]上的匹配，可以改进对匹配的搜索。

然而，我认为这更多的是性能优化而不是算法改进。比较的次数应该减少，但是算法的顺序应该是相同的。

编辑2009-10-1800:45

另一个优化发生在我身上，与将候选人分为偶数和奇数的做法一样。由于这三个索引必须与3的倍数相加(a，a + x，a + 2 x —— mod 3是0，与 a 和 x 无关) ，因此可以将 L、 M 和 U 分解成它们的 mod 3值:

事实上，你可以把这个和偶数/奇数的观察结果结合起来，把它们分成它们的 mod 6值:

这将提供进一步的性能优化，而不是算法加速。

小开

我想在发布第22个天真的解决方案之前，我应该加上一条评论。对于简单的解决方案，我们不需要显示字符串中1的个数最多为 O (log (n)) ，而是最多为 O (sqrt (n * log (n))。

答案:

def solve(Str):
indexes=[]
#O(n) setup
for i in range(len(Str)):
if Str[i]=='1':
indexes.append(i)


#O((number of 1's)^2) processing
for i in range(len(indexes)):
for j in range(i+1, len(indexes)):
indexDiff = indexes[j] - indexes[i]
k=indexes[j] + indexDiff
if k<len(Str) and Str[k]=='1':
return True
return False

它基本上有点类似于 Flybywire 的想法和实现，不过是向前看而不是向后看。

贪婪的弦建造者:

#assumes final char hasn't been added, and would be a 1
def lastCharMakesSolvable(Str):
endIndex=len(Str)
j=endIndex-1
while j-(endIndex-j) >= 0:
k=j-(endIndex-j)
if k >= 0 and Str[k]=='1' and Str[j]=='1':
return True
j=j-1
return False






def expandString(StartString=''):
if lastCharMakesSolvable(StartString):
return StartString + '0'
return StartString + '1'


n=1
BaseStr=""
lastCount=0
while n<1000000:
BaseStr=expandString(BaseStr)
count=BaseStr.count('1')
if count != lastCount:
print(len(BaseStr), count)
lastCount=count
n=n+1

(在我看来，我仍处于“学习蟒蛇”的理解阶段)

另外，从贪婪的字符串建设的潜在有用的输出，有一个相当一致的跳跃后，触及2的1的数量... 我不愿意等待，目睹触及2096。

strlength   # of 1's
1    1
2    2
4    3
5    4
10    5
14    8
28    9
41    16
82    17
122    32
244    33
365    64
730    65
1094    128
2188    129
3281    256
6562    257
9842    512
19684    513
29525    1024

小开

我会试着用数学的方法。这更像是一个开始而不是结束，所以任何帮助，评论，甚至矛盾-将深受感激。但是，如果这种方法被证明-该算法是在字符串中直接搜索。

给定一个固定数目的空格 k和一个字符串 S，搜索一个 k 空格的三联体需要 O(n)-如果 S[i]==S[i+k]==S[i+2k]，我们简单地测试每个 0<=i<=(n-2k)。测试取 O(1)，我们做 n-k次，其中 k是一个常数，所以它取 O(n-k)=O(n)。
让我们假设在 1的数目和我们需要搜索的最大空间之间存在一个逆比例。也就是说，如果有很多的 1，那么一定有一个三重态，而且它必须是相当密集的; 如果只有很少的 1，那么三重态(如果有的话)可能是相当稀疏的。换句话说，我可以证明，如果我有足够的 1，这样的三重态必须存在-我有更多的 1，一个更密集的三重态必须找到。这可以由鸽巢原理来解释——希望以后能详细阐述。
假设有一个上限 k，关于我需要寻找的可能的空间数。现在，对于位于 S[i]中的每个 1，我们需要检查 S[i-1]和 S[i+1]、 S[i-2]和 S[i+2]、 ... ... S[i-k]和 S[i+k]中的 1。由于 14，12中的每个 1都需要 10。请注意，这与第1节不同-我将 k作为空间数量的上界，而不是作为常量空间。

我们需要证明 O(n*log(n))，也就是说，我们需要证明 k*(number of 1's)与 log(n)成正比。

如果我们可以做到这一点，那么算法就很简单了——对于 S中索引为 i的每个 1，只需从每一侧查找到距离为 k的 1。如果在相同的距离发现两个，返回 i和 k。同样，棘手的部分是找到 k并证明其正确性。

我真的很感谢你的意见在这里-我一直试图找到之间的关系，k和 1的数量在我的白板上，到目前为止没有成功。

小开

下面是一个解决方案。可能会有一些小错误，这里和那里，但这个想法是合理的。

编辑: 它不是 n * log (n)

伪代码:

foreach character in the string
if the character equals 1 {
if length cache > 0 { //we can skip the first one
foreach location in the cache { //last in first out kind of order
if ((currentlocation + (currentlocation - location)) < length string)
if (string[(currentlocation + (currentlocation - location))] equals 1)
return found evenly spaced string
else
break;
}
}
remember the location of this character in a some sort of cache.
}


return didn't find evenly spaced string

C # 代码:

public static Boolean FindThreeEvenlySpacedOnes(String str) {
List<int> cache = new List<int>();


for (var x = 0; x < str.Length; x++) {
if (str[x] == '1') {
if (cache.Count > 0) {
for (var i = cache.Count - 1; i > 0; i--) {
if ((x + (x - cache[i])) >= str.Length)
break;


if (str[(x + (x - cache[i]))] == '1')
return true;
}
}
cache.Add(x);
}
}


return false;
}

工作原理:

iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache


iteration 2:
x
|
101101001


iteration 3:
a x b
| | |
101101001
//we retrieve location a out of the cache and then based on a
//we calculate b and check if te string contains a 1 on location b


//and of course we store x in the cache because it's a 1


iteration 4:
axb
|||
101101001


a  x  b
|  |  |
101101001




iteration 5:
x
|
101101001


iteration 6:
a x b
| | |
101101001


a  x  b
|  |  |
101101001
//return found evenly spaced string

小开

使用 O (n ^ 2)空间的简单 O (n)解怎么样? (使用所有位运算符都在 O (1)中工作的假设。)

该算法基本上分为四个阶段:

第一阶段: 对于原始数字中的每一位，找出它们之间的距离，但只考虑一个方向。(我考虑了最不重要位方向上的所有位。)

阶段2: 反转输入位的顺序;

阶段3: 在反向输入上重新运行步骤1。

第四阶段: 比较第一阶段和第三阶段的结果。如果任何位的上下间距相等，我们必须有一个命中。

请记住，在上述算法中，没有一个步骤需要比 O (n)更长的时间。 ^ _ ^

作为一个额外的好处，这个算法将找到所有相等间隔的每个数字。例如，如果你得到一个“0x0005”的结果，那么在1和3个单位之间的距离是相等的

我并没有真正尝试优化下面的代码，但是可编译的 C # 代码似乎可以工作。

using System;


namespace ThreeNumbers
{
class Program
{
const int uint32Length = 32;


static void Main(string[] args)
{
Console.Write("Please enter your integer: ");
uint input = UInt32.Parse(Console.ReadLine());


uint[] distancesLower = Distances(input);
uint[] distancesHigher = Distances(Reverse(input));


PrintHits(input, distancesLower, distancesHigher);
}


/// <summary>
/// Returns an array showing how far the ones away from each bit in the input.  Only
/// considers ones at lower signifcant bits.  Index 0 represents the least significant bit
/// in the input.  Index 1 represents the second least significant bit in the input and so
/// on.  If a one is 3 away from the bit in question, then the third least significant bit
/// of the value will be sit.
///
/// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.
/// (Where n is the number of bits in the input.)
/// </summary>
public static uint[] Distances(uint input)
{
uint[] distanceToOnes = new uint[uint32Length];
uint result = 0;


//Sets how far each bit is from other ones. Going in the direction of LSB to MSB
for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
distanceToOnes[arrayIndex] = result;
result <<= 1;


if ((input & bitIndex) != 0)
{
result |= 1;
}
}


return distanceToOnes;
}


/// <summary>
/// Reverses the bits in the input.
///
/// As programmed this algorithm needs O(n) time and O(n) space.
/// (Where n is the number of bits in the input.)
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static uint Reverse(uint input)
{
uint reversedInput = 0;
for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
{
reversedInput <<= 1;
reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
}


return reversedInput;
}


/// <summary>
/// Goes through each bit in the input, to check if there are any bits equally far away in
/// the distancesLower and distancesHigher
/// </summary>
public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
{
const int offset = uint32Length - 1;


for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
{
//hits checks if any bits are equally spaced away from our current value
bool isBitSet = (input & bitIndex) != 0;
uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];


if (isBitSet && (hits != 0))
{
Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
}
}
}
}
}

有些人可能会评论说，对于任何足够大数字，按位运算不能在 O (1)中完成。你说得对。然而，我推测每个使用加法、减法、乘法或除法的解决方案(不能通过移位来实现)也会有这个问题。

小开

显然，我们至少需要在同一时间检查多个三胞胎，所以我们需要以某种方式压缩检查。我有一个候选算法，但分析时间复杂度超出了我的能力 * 时间阈值。

构建一个树，其中每个节点有三个子节点，每个节点的叶子上包含总数为1的子节点。在1上建立一个链表。为每个节点分配与其覆盖范围成比例的允许成本。只要我们在每个节点上花费的时间在预算范围内，我们就会有一个 O (n lg n)算法。

--

从根开始。如果总数1的平方低于它的允许成本，应用幼稚算法。否则对其子级进行递归。

现在，我们要么在预算内返回，要么我们知道没有有效的三胞胎完全包含在一个孩子。因此，我们必须检查节点间的三元组。

现在事情变得一团糟。我们实际上想要递归到子集的潜在集合上，同时限制范围。一旦范围受到足够的限制，使得初始算法可以在预算内运行，就可以开始了。享受实现它的过程吧，因为我保证它将是乏味的。大概有十几个案子。

--

我认为这个算法可行的原因是因为没有有效三联体的序列似乎在1和大量0之间交替出现。它有效地分裂了附近的搜索空间，并且树模拟了这种分裂。

算法的运行时间根本不明显。它依赖于序列的非平凡属性。如果1真的是稀疏的，那么幼稚的算法将在预算下工作。如果1是稠密的，那么应该马上找到一个匹配。但是，如果密度是“刚刚好”(例如，接近 ~ n ^ 0.63，你可以通过设置所有位的位置没有’2’数字在基数3) ，我不知道它是否会工作。你必须证明分裂效应足够强。

小开

这里没有理论上的答案，但是我编写了一个快速的 Java 程序来研究作为 k 和 n 的函数的运行时行为，其中 n 是总位长度，k 是1的数字。我同意一些回答者的观点，他们认为“正则”算法检查所有的位位置对并寻找第三位，即使在最坏的情况下需要 O (k ^ 2) ，实际上因为最坏的情况需要稀疏的位字符串，这个算法是 O (n ln n)。

不管怎样，下面是程序。这是一个蒙特卡洛风格的程序，运行了大量的试验 NTRIALS 常数 n，并随机生成比特集的 k 值范围使用伯努利进程与1-密度约束之间的限制，可以指定，并记录运行时间寻找或未能找到一个均匀间隔的三元组，时间测量的步骤不在 CPU 时间。我运行了 n = 64,256,1024,4096,16384 * (仍在运行) ，首先是500000次测试，看看哪个 k 值运行时间最长，然后是另一个测试，5000000次测试，缩小一个密度集中看看这些值是什么样子。最长的运行时间确实发生在非常稀疏的密度(例如，对于 n = 4096，运行时间峰值在 k = 16-64范围内，平均运行时间峰值为4212步@k = 31，最大运行时间峰值为5101步@k = 58)。看起来，最坏情况下的 O (k ^ 2)步要变得比 O (n)步更大需要非常大的 N 值，在 O (n)步中，你需要扫描位字符串来找到1的位置索引。

package com.example.math;


import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;


public class EvenlySpacedOnesTest {
static public class StatisticalSummary
{
private int n=0;
private double min=Double.POSITIVE_INFINITY;
private double max=Double.NEGATIVE_INFINITY;
private double mean=0;
private double S=0;


public StatisticalSummary() {}
public void add(double x) {
min = Math.min(min, x);
max = Math.max(max, x);
++n;
double newMean = mean + (x-mean)/n;
S += (x-newMean)*(x-mean);
// this algorithm for mean,std dev based on Knuth TAOCP vol 2
mean = newMean;
}
public double getMax() { return (n>0)?max:Double.NaN; }
public double getMin() { return (n>0)?min:Double.NaN; }
public int getCount() { return n; }
public double getMean() { return (n>0)?mean:Double.NaN; }
public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; }
// some may quibble and use n-1 for sample std dev vs population std dev
public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
for (int i = 0; i < statistics.length; ++i)
{
StatisticalSummary summary = statistics[i];
ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
i,
summary.getCount(),
summary.getMin(),
summary.getMax(),
summary.getMean(),
summary.getStdDev());
}
}
}


public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
{
public void setProbability(double d);
public boolean getNextBoolean();
}


static public class Bernoulli implements RandomBernoulliProcess
{
final private Random r = new Random();
private double p = 0.5;
public boolean getNextBoolean() { return r.nextDouble() < p; }
public void setProbability(double d) { p = d; }
}
static public class TestResult {
final public int k;
final public int nsteps;
public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; }
}


////////////
final private int n;
final private int ntrials;
final private double pmin;
final private double pmax;
final private Random random = new Random();
final private Bernoulli bernoulli = new Bernoulli();
final private BitSet bits;
public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
this.bits = new BitSet(n);
}


/*
* generate random bit string
*/
private int generateBits()
{
int k = 0; // # of 1's
for (int i = 0; i < n; ++i)
{
boolean b = bernoulli.getNextBoolean();
this.bits.set(i, b);
if (b) ++k;
}
return k;
}


private int findEvenlySpacedOnes(int k, int[] pos)
{
int[] bitPosition = new int[k];
for (int i = 0, j = 0; i < n; ++i)
{
if (this.bits.get(i))
{
bitPosition[j++] = i;
}
}
int nsteps = n; // first, it takes N operations to find the bit positions.
boolean found = false;
if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
{
int lastBitSetPosition = bitPosition[k-1];
for (int j1 = 0; !found && j1 < k; ++j1)
{
pos[0] = bitPosition[j1];
for (int j2 = j1+1; !found && j2 < k; ++j2)
{
pos[1] = bitPosition[j2];


++nsteps;
pos[2] = 2*pos[1]-pos[0];
// calculate 3rd bit index that might be set;
// the other two indices point to bits that are set
if (pos[2] > lastBitSetPosition)
break;
// loop inner loop until we go out of bounds


found = this.bits.get(pos[2]);
// we're done if we find a third 1!
}
}
}
if (!found)
pos[0]=-1;
return nsteps;
}


/*
* run an algorithm that finds evenly spaced ones and returns # of steps.
*/
public TestResult run()
{
bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
// probability of bernoulli process is randomly distributed between pmin and pmax


// generate bit string.
int k = generateBits();
int[] pos = new int[3];
int nsteps = findEvenlySpacedOnes(k, pos);
return new TestResult(k, nsteps);
}


public static void main(String[] args)
{
int n;
int ntrials;
double pmin = 0, pmax = 1;
try {
n = Integer.parseInt(args[0]);
ntrials = Integer.parseInt(args[1]);
if (args.length >= 3)
pmin = Double.parseDouble(args[2]);
if (args.length >= 4)
pmax = Double.parseDouble(args[3]);
}
catch (Exception e)
{
System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
System.exit(0);
return; // make the compiler happy
}


final StatisticalSummary[] statistics;
statistics=new StatisticalSummary[n+1];
for (int i = 0; i <= n; ++i)
{
statistics[i] = new StatisticalSummary();
}


EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
int printInterval=100000;
int nextPrint = printInterval;
for (int i = 0; i < ntrials; ++i)
{
TestResult result = test.run();
statistics[result.k].add(result.nsteps);
if (i == nextPrint)
{
System.err.println(i);
nextPrint += printInterval;
}
}
StatisticalSummary.printOut(System.out, statistics);
}
}

小开

最佳答案

终于来了！跟踪电视台的回答中的线索，我们得到了它: 用 O (n log n)算法解决这个问题！这也很简单，在你理解之后。猜测 FFT 的人是对的。

问题是: 我们得到了一个长度为 N的二进制字符串 S，我们想在其中找到三个等间距的1。例如，S可能是 110110010，其中 N = 9。它在位置2、5和8上均匀地放置了1。

从左到右扫描 S，列出位置为1的 L。对于上面的 S=110110010，我们有列表 L = [1,2,4,5,8]。这一步是 O (n)。现在的问题是在 L中找到一个 等差数列，也就是在 L中找到不同的 A b c，使得 B-a = c-b，或者相当于 A + c = 2b 。对于上面的例子，我们想要找到级数(2,5,8)。
为 L中的每个 K制作一个带有术语 X k 的 多项式 p。对于上面的例子，我们使多项式 P (x) = (x + x 2 + x 4 + x 5 + x 8 )。这一步是 O (n)。
使用快速傅里叶变换求出多项式 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
对于 L中的某些 K，忽略除了与 X 2k 对应的术语之外的所有术语。对于上面的例子，我们得到术语 X 16 ，3 x 10 ，x 8 ，x 4 ，x 2 。这个步骤是 O (n) ，如果你选择这么做的话。

这是关键点: L中 B的 X 2b 系数是 完全正确，L中 (a，c)对的数目，这样 A + c = 2b。[ CLRS，Ex.一个这样的对是 (b，b)总是(所以系数至少是1) ，但如果存在任何其他对 (a，c)，那么系数至少是3，从 (a，c)和 L0。对于上面的例子，由于 AP (2,5,8) ，我们使得 L1的系数精确地为3。(由于上述原因，这些系数 X 2b 总是奇数。Q 中的所有其他系数都是偶数。)

那么，算法就是查看这些术语 X 2b 的系数，看看它们中是否有大于1的。如果没有，那么就没有均匀间隔的1。如果 L中的是 a B的 X 2b 系数大于1，那么我们知道除了 (b，b)以外，还有一对 (a，c)的 A + c = 2b。要找到实际的对，我们只需尝试 L中的每个 L0(对应的 L1是 L2) ，并查看在 S中的位置 L2是否有1。这一步是 O (n)。

就这样，各位。

有人可能会问: 我们需要使用 FFT 吗？许多答案，例如贝塔的，无线飞行器和 RSP 的，表明这种方法，检查每一对1，看看是否有一个1在“第三”的位置，可能在 O (n log n) ，基于直觉，如果有太多的1，我们会很容易找到一个三倍，如果有太少的1，检查所有对花费很少的时间。不幸的是，尽管这种直觉是正确的，而且简单的方法是比 O (n²)更好，但它并没有明显更好。如同在电视台的回答中，我们可以取长度为 N = 3 k 的字符串的“ Cantor-like 集合”，在三元表示中只有0和2s (没有1s)的位置上有1s。这样的字符串中有 2 k = n (log 2)/(log 3) ≈ n 0.63 字符串，而且没有间隔均匀的1s 字符串，所以检查所有对的次序都是1s 字符串的平方: 这就是 4 k ≈ n 1.26 ，不幸的是它的渐近大于(n log n)。事实上，最糟糕的情况甚至更糟: Leo Moser 在1953年的建造中(有效地)使用了这样的字符串，它们中有无线飞行器01s，但是没有等间距的1s，这意味着对于这样的字符串，简单的方法只能使用无线飞行器1ーー只有一个无线飞行器2比 Θ (n²) 好一点，令人惊讶！

大约一个长度为 n 的字符串中最大的1个数，没有3个间隔相等的字符串(我们在上面看到的至少是从简单的 Cantor 式结构中得到的 N 0.63 ，至少是用 Moser 式结构得到的 N 1-c/√(log n) )ーー这就是 OEIS A003002。也可以由 OEIS A065825直接计算为 k，使 A065825(k)≤ n < A065825(k + 1)。我编写了一个程序来查找这些字符串，结果发现贪婪算法没有给出的字符串最长。例如，对于 N = 9，我们可以得到5个1(110100011) ，但是贪婪者只给出4个(110110000) ，对于 N = 26，我们可以得到11个1(110010100010110001101) ，但是贪婪者只给出8个(1101100001101100000000000) ，而对于 N = 74，我们可以得到22个1(110000101100010000100000101101000000101010000000000000010000011010000000011)但是贪婪者只给出了16(11011000000000000000000110110000000011011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000。不过，他们确实在很多地方达成了一致，直到50岁(例如38岁到50岁之间的所有人)。正如 OEIS 参考资料所说，雅罗斯瓦夫 · 罗布莱夫斯基似乎对这个问题很感兴趣，他在这些非平均集非平均集上维护了一个网站。确切的数字只有194个。

小开

# <algorithm>
def contains_evenly_spaced?(input)
return false if input.size < 3
one_indices = []
input.each_with_index do |digit, index|
next if digit == 0
one_indices << index
end
return false if one_indices.size < 3
previous_indexes = []
one_indices.each do |index|
if !previous_indexes.empty?
previous_indexes.each do |previous_index|
multiple = index - previous_index
success_index = index + multiple
return true if input[success_index] == 1
end
end
previous_indexes << index
end
return false
end
# </algorithm>


def parse_input(input)
input.chars.map { |c| c.to_i }
end

我对最坏的情况下数以百万计的数字有困难。从 /dev/urandom模糊化基本上给你 O (n) ，但我知道最坏的情况是更糟糕的。我只是不知道有多糟糕。对于小型的 n，在 3*n*log(n)附近找到输入是微不足道的，但是对于这个特殊的问题，很难区分这些输入和其他的增长顺序。

任何处理最坏情况输入的人能生成一个长度大于10万的字符串吗？