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

好的，我要再试一次解决这个问题。我认为我可以证明一个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))的时间内完成。

我有遗漏什么吗？

对于简单的问题类型（即在三个“1”之间只有（即零个或多个）“0”），很简单：您可以在每个“1”处拆分序列，并查找具有相同长度的两个相邻子序列（第二个子序列不是最后一个）。当然，这可以在O(n)时间内完成。

对于更复杂的版本（即搜索索引i和间隔g>0，使得s[i]==s[i+g]==s[i+2*g]=="1"），我不确定是否存在O(n log n)解决方案，因为可能存在O(n²)具有此属性的三元组（考虑全为1的字符串，大约有n²/2这样的三元组）。当然，您只需要寻找其中的一个，但我目前不知道如何找到它...

我想到了一种可能有效的分治方法。

首先，在预处理中，您需要将所有小于输入大小的一半（n/3）的数字插入到列表中。

给定一个字符串：0000010101000100（请注意，此特定示例是有效的）

将1到（16/2）之间的所有质数（和1）插入到列表中：{1, 2, 3, 4, 5, 6, 7}

然后将其分成两半：

100000101 01000100

继续这样做，直到得到大小为1的字符串。对于所有包含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。

将其重新组合成四组四个，我们有：

1000：返回（0，{4,5,6,7}） 0101：返回（5，{2,3,4,5,6,7}），（7，{1,2,3,4,5,6,7}） 0100：返回（9，{3,4,5,6,7}） 0100：返回（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}） 01000100：返回（9，{4,7}），（13，{3,4,5,6,7}）

组合成一个十六个元素的集合：

10000101 01000100

随着我们的进展，我们不断地检查到目前为止的所有可能性。在这一步中，我们留下了超出字符串结尾的东西，但现在我们可以检查所有的可能性。
基本上，我们检查第一个1和5和7的间距，发现它们没有对齐1。 （请注意，每个检查是CONSTANT，而不是线性时间）然后我们使用2、3、4、5、6和7的间距检查第二个（索引5的位置），或者我们会停在2，因为那实际上匹配起来了。
哇！那是一个相当长的算法。
我不知道它是否100%是O(n log n)，因为最后一步，但是就我所知，直到那里的一切肯定都是O(n log n)。稍后我会回来并尝试完善最后一步。
编辑：更改我的答案以反映Welbog的评论。对于错误表示抱歉。等我再次解密我写的内容时，我会稍后写一些伪代码。;-)

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

我假设111000001会找到前三个1并成功。实际上，跟随1后面的零的数量是重要的，因为根据您的定义，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和0组成的字符串与其自身的移位版本进行比较。然后取匹配的1。以下是一个移位两位的示例：

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

结果为1的位（按位与）必须表示那些间隔为2的所有1。同样的例子向右移三位：

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

在此情况下，没有1的间隔恰好为3。
那么这告诉你什么呢？那就是你只需要测试素数位移。例如，假设你有两个间隔为6的1，则只需测试“二”位移和“三”位移（因为它们可以整除6）。例如：

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，注意它在取模位置后的余数。模数范围从1到字符串大小的一半。这是因为最大可能的分离大小是字符串的一半。这是在O(n^2)中完成的。但是。只需要检查素数模数，所以是O(n^2/log(n))
2. 按最大模数的顺序对模数/余数列表进行排序，这可以在O(n*log(n))时间内完成。
3. 查找三个连续的相同模数/余数。
4. 以某种方式检索出1的位置！

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

错误

同事指出，步骤1是错误的。如果我们在位置2、12和102处有1，则对10取模，它们将具有相同的余数，但它们并不等间隔！抱歉。

我认为这个算法的时间复杂度是O(nlogn)，原因如下：

• 要找到三元组中第一个1，你需要检查(n-2)个字符。如果在这之前没有找到，那么你就不会找到了（因为第n-1和第n个字符不能作为三元组的开头）(O(n))
• 要找到三元组中第二个1（由第一个1开始），你需要检查m/2个字符（其中m=n-x，x是第一个1的偏移量）。这是因为，如果你在从第一个1到结尾的一半的位置还没有找到第二个1，那么你就不会找到了...因为第三个1必须恰好在第二个1的同样距离之后。(O(log(n)))
• 找到最后一个1的时间复杂度是O(1)，因为当你找到第一个和第二个1时，你已经知道它必须在哪个索引处。

因此，总的时间复杂度为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

我认为我已经找到了解决问题的方法，但我无法构建正式的证明。 我制作的解决方案是用Java编写的，并使用计数器“n”来计算它执行了多少次列表/数组访问。 因此，如果正确，则n应小于或等于stringLength * log（stringLength）。 我尝试了数字0到2 ^ 22，它有效。

它从迭代输入字符串开始，并创建一个包含所有包含1的索引的列表。 这只是O（n）。

然后从索引列表中选择一个firstIndex和一个大于firstIndex的secondIndex。 这两个索引必须保持为1，因为它们在索引列表中。 从那里可以计算出thirdIndex。 如果inputString [thirdIndex]为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)，因此它对算法复杂度没有影响。

在扫描1s时，将它们的位置添加到列表中。当添加第二个及其后续的1s时，将它们与迄今为止列表中的每个位置进行比较。间距等于currentOne（中心）-previousOne（左）。右侧位是currentOne + spacing。如果是1，则结束。

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. 去掉前导和尾随零。
2. 扫描字符串查找1。
3. 当找到1时：
   1. 假设它是解决方案的中间1。
   2. 对于每个之前的1，使用其保存的位置计算最终1的预期位置。
   3. 如果计算出的位置在字符串的末尾之后，则它不能成为解决方案，因此从候选列表中删除该位置。
   4. 检查解决方案。
4. 如果未找到解决方案，则将当前1添加到候选列表中。
5. 重复直到不再找到1。

现在考虑像以下这样的输入字符串，它们将没有解决方案：

101
101001
1010010001
101001000100001
101001000100001000001

通常，这是形如j个0紧随其后的1的k个字符串的串联，其中j从零到k-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";

在发布第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

（为自己辩护，我仍处于“学习Python”的阶段）

此外，在贪婪地构建字符串时，命中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