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

Question

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

algorithmbig-o

177

我昨天在算法测试中遇到了这个问题，但我无法找出答案，这让我非常疯狂，因为它占了大约40分。我觉得大多数同学没有正确解决它，因为我过去24小时内也没有找到解决方案。

给定长度为n的任意二进制字符串，如果存在三个等间距的1，请编写一个算法在O(n*log(n))的时间内解决此问题。

像这样的字符串有三个“等间距”的1：11100000、0100100100

编辑：这是一个随机数，所以它应该适用于任何数字。我给出的例子是为了说明“等间距”属性。因此，1001011是一个有效的数字，其中1、4和7是等间距的1。

- Robert Parker

4

以下是否可能：10011010000？它有三个1（第一、二、四位）等间距分布，但也有额外的1。 - Anna

5

Robert，你需要让你的教授给你答案，并在这里发布。这个问题让我烦透了。我能够想出n^2的解法，但不是n*log(n)的。 - James McMahon

3

嗯，我也花了很长时间试图弄清楚这个问题，但仍然没有找到一个好的答案。也许你误解了问题？例如，如果问题是寻找一种运行时间为O(n log n)的算法，用于确定一个间隔为k的均匀序列在一个更大的序列中的位置，这可以使用快速傅里叶变换轻松完成。 - ldog

5

考虑到 Klaus Roth 在 1958 年因证明每个密度 d>0 都存在一个自然数 N，使得 {1,...,N} 的任何至少包含 d*N 个元素的子集都包含长度为 3 的等差数列而获得菲尔兹奖章，我并不惊讶目前还没有人找到令人信服的算法来解决这个问题。另请参见 http://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem - j.p.

2

ShreevatsaR的回答使得这个问题成为SO上最好的算法问题之一。 - Bob Aman

显示剩余23条评论

31个回答

36

您的问题被称为《论算术平均数问题》(1999)中的AVERAGE问题。此文献指出，如果可以从3SUM问题进行次二次规约，则该问题称为3SUM-hard问题：给定一个由n个整数组成的集合A，是否存在a、b、c在A中，使得a+b+c=0？目前尚不清楚AVERAGE问题是否为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^2)更快的算法，并且据推测，不存在更快的算法。所有未考虑这一点的人都在尝试解决一个开放问题。

其他有趣的信息，大多数与本题无关：

下限：

一个简单的下界是 Cantor 集（其中数字为 1 到 3^n-1，且其三进制展开式中不包含 1）--它的密度为 n^(log_3 2)（约为0.631）。所以只检查集合大小不太大，然后检查所有成对关系是不足以得到 O(n log n) 的时间复杂度的。您必须更加聪明地研究这个序列。更好的下界是在这里引用的 - 它是 n^{1-c/(log(n))^(1/2)}，这意味着 Cantor 集不是最优的。

上限 - 我的老算法：

已知对于大的 n，不含有等差数列的 {1,2,...,n} 的子集最多有 n/(log n)^(1/20) 个元素。文章 “On triples in arithmetic progression”证明了更多情况：该集合不能超过 n * 2²⁸ * (log log n / log n)^1/2 元素。因此，你可以检查是否达到了该界限，如果没有，那么就朴素地检查成对关系。这是一个 O(n² * log log n / log n) 的算法，比 O(n²) 要快。不幸的是，“On triples...”在 Springer 上，但第一页可以看到，Ben Green 的解释在这里，第28页，定理24。

顺便说一下，这些论文都是从 1999 年开始的 - 和我提到的第一个论文一样，所以那篇论文可能没有提到那个结果。

- sdcvvc

2

很好的答案，第一个对这个问题做出明确回答。因此，Cantor-like集合有n^0.63个1，这意味着“检查所有1对”的算法在最坏情况下至少为n^1.26（≫ n log n）。 Szemeredi论文中引用的下限（顺便提一句，他引用的Moser论文在这里可用：http://books.google.com/books?id=Cvtwu5vVZF4C&pg=PA245）似乎实际上意味着n^(2-o(1))，但我们必须稍微小心，因为这里的数字是序列中数字的*总和*，而不是从{1，...，n}中选择的数字。 - ShreevatsaR

嗯，"Cantor-like" 二进制序列到底是什么？它包含 n^(log_3 2) 个 1，并且没有三个等间距的 1。 - ShreevatsaR

这是一个长度为3^n的二进制字符串，其中有2^n个1（密度为n^0.63）。如果你用二进制写下1的位置，它将是{0,2,20,22,200,202,220,222}。另一种可能的想法是取一个1的序列，并像正常的Cantor集构造一样不断删除“中间”的1：111111111 -> 111000111 -> 101000101。它不包含算术级数的原因是：如果x、y、z形成一个算术级数，则y=(x+z)/2，而x和z在某些扩展位上不同。取最高位。假设x有0，z有2。那么y必须在那里有1。矛盾。 - sdcvvc

3

太棒了，好的研究成果！我追踪了2008年的3SUM论文，并查阅了CLRS习题30.1-7，看完之后我得到了答案——O(n log n)算法实际上非常简单！（只需要将一个多项式平方/生成函数。）我已经在下面张贴了答案。（现在为自己没有早些想到它而感到遗憾……简单的解决方案总是引发这种反应:p） - ShreevatsaR

太棒了，好答案。研究得真不错。我看过所有我见过的字符串匹配算法，但这个完全是新奇的。 - wheaties

显示剩余3条评论

8

这不是一个解决方案，但与Olexiy的想法类似

我正在尝试创建具有最大数量“1”位的序列，它们都非常有趣，我已经达到了125个数字，以下是尝试插入尽可能多的“1”位所找到的前3个数字：

11011000011011000000000000001101100001101100000000000000000000000000000000000000000110110000110110000000000000011011000011011
10110100010110100000000000010110100010110100000000000000000000000000000000000000000101101000101101000000000000101101000101101
10011001010011001000000000010011001010011001000000000000000000000000000000000000010011001010011001000000000010011001010011001

请注意，它们都是分形（考虑到限制条件，这并不奇怪）。也许反向思考会有所帮助，如果字符串不是具有特征的分形，那么它必须具有重复的模式？

感谢Beta提供更好的术语来描述这些数字。

更新：不幸的是，当以足够大的初始字符串开始时（例如：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

- z -

2

天啊，这些是分形图！如果这个成立，它将对1的数量设定一个上限，而且它小于O(n)。 - Beta

分形，这是一个更好的术语来描述它们。谢谢。 - z -

有趣的是，这些模式与康托三分集（http://en.wikipedia.org/wiki/Cantor_set）非常相似。如果是这样的话，那么1的比例必须趋近于零... - flybywire

最大数量的序列中没有三个连续1的是否直接与算法的最坏运行时间相关？有可能出现包含大量1但是只在很晚才发现三个连续1的字符串，因为这些1位于算法晚期检查的位置。 - ShreevatsaR

3

我的分析表明，在字符串中出现的“1”的个数与整个字符串的大小相比存在线性关系。这使我认为，对于给定的字符串，不存在一个幸福的上限让我们说字符串中“1”的数量最多为log(n)。因此，只涉及“1”位置而不涉及整个字符串本身的解决方案将是O(n^2)，更准确地说，是O(n+m^2)，其中m是字符串中“1”的数量，n是字符串大小，且m是big-theta(n)。 - Welbog

我观察到，在n长度的二进制字符串集中，需要最多迭代次数来检查的候选者是那些具有3/8到5/8个1的候选者。在17个字符之后，最坏情况下候选者的1长度/总长度会降至50%以下。这里没有科学，只有观察结果。 - hughdbrown

6

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

我想出了一些模糊的论点，但我还没有找到一个整洁的证明。我要冒个险：答案是一个非常聪明的想法，教授已经知道这个想法很长时间了，以至于它似乎是显而易见的，但它对学生来说太难了。（或者你可能在讲座中睡着了）。

- Beta

2

哈哈，我没有睡过任何课程。我和其他几个学生交流了一下，但是没有人有清晰的解决方案。大多数人写了一些关于分治的废话，希望能得到一些部分分。 - Robert Parker

3

修订日期：2009年10月17日23: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月16日18:48

对于yx提供的数据，其他回答认为这是代表可计算硬数据的数据，我得到了以下结果... 我已将其删除。它们已经过时。

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

编辑：2009年10月17日13: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 []分成奇数和偶数池，并依次在奇数和偶数候选池中搜索匹配项，可以改进匹配的搜索。但我认为这更多是性能优化而不是算法改进。比较的数量应该会减少，但算法的顺序应该是相同的。

编辑时间 2009-10-18 00:45

我想到了另一个优化方案，与将候选人分为偶数和奇数的方案类似。由于三个索引必须加起来是3的倍数（a、a+x、a+2x - 不考虑a和x时mod 3等于0），因此您可以将L、M和U分成它们的mod 3值：

事实上，您可以将这个与奇偶观察相结合，并将它们分成它们的模6值：

等等。这将提供进一步的性能优化，但不会提高算法速度。

- hughdbrown

2

目前还没有找到解决方案 :(，但有一些想法。

如果我们从一个相反的问题开始：构造一个序列，其中包含最多数量的1，且没有任何均匀间隔的三元组。如果您可以证明最大数量的1是o(n)，那么您可以通过仅迭代只有1的列表来改进您的估计。

- Olexiy

好的，1的数量肯定受到O(n)的限制。它不可能是O(n ** 2)，对吧——1的数量增长比数据快？重要的问题是上限是否低于那个。 - hughdbrown

我使用了小写字母 o，而不是大写字母 O。 - Olexiy

2

这可能有所帮助...

问题可以简化为：

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

例如，给定序列 [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ]，我们可以找到一个子序列 [ 3, 6, 5, 2, 2 ]，其中前缀为 [ 3, 6 ]，其前缀和为 9，后缀为 [ 5, 2, 2 ]，其后缀和为 9。

以下是简化的方法：

给定一个由0和1组成的序列，从最左边的1开始向右移动。每次遇到另一个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)。

不幸的是，我不确定从这里该如何继续。

- yfeldblum

1

这是一种更紧凑的表示法，但它不会改善时间复杂度。 "前缀"分区集等同于在所有"1"出现的位置上进行全对搜索，其时间复杂度为 O(n^2)。 - p00ya

显然，有一些算法处理连续子序列和。不幸的是，它们似乎都在O(n)中找到具有最大总和的连续子序列。 - yfeldblum

@p00ya 这不是正确的。使用此算法，时间复杂度取决于错误位数的上限，在Cantor生成的字符串假设下为((3/2)^(log(n)/log(3)))，空间复杂度随之产生，但时间复杂度变为乘以n。请查看我的第二个答案（不是负的）:D - Luka Rahne

@ralu：那是基于你的假设，Cantor生成的字符串是最坏情况，这是错误的。据记录，成对数肯定是O（n ^ 2）;但我想我真正意味着它是big-Omega（n ^ 2），考虑到这些结果(尤其是NrootN链接)，表明了证明成对数的下限是big-Omega（n ^（2/1.52））或大Omega（n ^（4/3））的猜测。 - p00ya

1

一个有趣的问题，但一旦你意识到两个“1”之间的实际模式并不重要，算法就变成了：

扫描查找“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;
 }
}

- rsp

4

如果我没错的话，这个算法的时间复杂度是O(n²)，因为外部循环运行了n次，而内部循环平均运行了n/2次。 - StriplingWarrior

外部循环运行n次，内部循环平均运行n/4次，但仅从跟随'1'的位置开始。为了接近n^2的行为，必须高频使用'1'，这会很早就得到一个true结果，从而停止处理。因此，n^2的行为将永远不会发生。如何根据已知数据属性确定O，目前我还无法解决。 - rsp

很遗憾，这不是关于平均实际运行时间的问题，而是关于理论上的大O运行时间。你的方法是O(n²)（与我的方法相同，因为你的方法与我的相同）。 - DaClown

我所说的不是平均行为，而是最大行为。如果可以证明未通过测试的最大熵在字符串中包含log n个“1”，我将不感到惊讶。 - rsp

如果您在外部循环中使用内部循环找到的第一个1的索引更新索引，即if (ones[m] == ONE) {n = m}，那会对大O有帮助吗？ - steamer25

你可以添加像这样的优化来稍微提高性能，但是外部循环已经快速跳过了“0”，所以我预计额外的代码只会让你改变找到的第一个“1”的外部索引，从而抵消了在外部循环中节省的时间。系统的整体行为不会改变。 - rsp

1

我会在这里给出我的大致猜测，并让那些更擅长计算复杂度的人帮助我判断我的算法在O-notation方面的表现如何

给定二进制字符串0000010101000100（以此为例）
裁剪头部和尾部的零 -> 00000 101010001 00
我们从上一次计算中得到了101010001
检查中间位是否为“1”，如果是，则找到了有效的三个等间距的“1”（仅当位数为奇数时）
相应地，如果剩余的裁剪位数为偶数，头部和尾部的“1”不能成为等间距的“1” 的一部分，
我们以1010100001为例（加一个额外的“0”变成偶数），在这种情况下，我们需要再次裁剪，然后变成 -> 10101 00001
我们从上一次计算中得到了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;
}

- andycjw

@recursive 请检查我添加的代码，以更好地解释我之前编写的伪代码，该伪代码不是非常严格和简洁。 - andycjw

这是nlogn的算法 - 对于n位，我们期望大约进行logn次迭代，检查n * c位，其中C是一个常数。 - Ron Warholic

是的，这似乎在111001和100111上失败了，因为最简单的情况下均匀间隔的1不必居中于中间位。 - Dean J

@sid，由于问题空间的原因，计算复杂度尤其困难。它不是像你提到的那样一次截去一个1，而是截取到下一个可用的“1”位，例如101010000001，在第一次尝试失败后，它将截取到10101，这是从末尾开始的下一个可用的“1”位；对于这个算法来说，很难想出更糟糕的情况，我能想到的最好的情况是1010100101010101.....01，这只需要O(n/2) = O(n)的时间复杂度，有人能给出更糟糕的情况吗？ - andycjw

是的，我明白。然而，即使进行了修改，我的第一条评论使用111100001111仍然有效...现在我不知道复杂度会是多少 :( - Matthieu M.

显示剩余7条评论

1

我想出了这样的代码：

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 - (len-2)（跳过最后一个字符）和 1 - (len-1)（跳过第一个字符）。
如果不是偶数，则如果中间字符为 1，则成功。否则，在不包括中间元素的情况下将字符串分成两部分并检查两个部分。

关于复杂度，这可能是 O(nlogn)，因为在每次递归中我们都要除以二。

希望能有所帮助。

- Beku

看起来你正在将一个包含N个元素的问题转化为两个包含N-1个元素的问题。将其对半分意味着将其转化为两个包含N/2个元素的问题。 - RHSeeger

这仅适用于偶数长度的情况。因此，如果长度为8，则算法创建长度为7、7、3、3、3、3的字符串。递归树的高度为3，等于lg(8)。 - Beku

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ShreevatsaR · Accepted Answer

终于！跟进sdcvvc的回答，我们有了解决这个问题的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 中找到一个长度为3的等差数列，即找到不同的 a、b、c，使得 b-a = c-b 或等价于 a+c=2b。对于上面的例子，我们要找到等差数列 (2, 5, 8)。
用每个 k 在 L 中制作一个多项式 p。对于上面的例子，我们制作多项式 p(x) = (x + x² + x⁴ + x⁵+x⁸)。这一步是 O(n) 的。
使用 Fast Fourier Transform 找到多项式 q = p²。对于上面的例子，我们得到多项式 q(x) = x¹⁶ + 2x¹³ + 2x¹² + 3x¹⁰ + 4x⁹ + x⁸ + 2x⁷ + 4x⁶ + 2x⁵ + x⁴ + 2x³ + x²。这一步是 O(n log n) 的。
忽略除了对于 L 中某些 k 对应的 x^2k 之外的所有项。对于上面的例子，我们得到了以下项：x¹⁶, 3x¹⁰, x⁸, x⁴, x²。如果选择执行此步骤，则此步骤是 O(n) 的。

这里的关键点在于：对于L中任意一个b的x^2b系数，其值恰好为L中满足a+c=2b的(a,c)对数。[CLRS, Ex. 30.1-7] 其中，(b,b)总是其中之一（因此系数至少为1），但如果存在其他的(a,c)对，则系数至少为3，来自于(a,c)和(c,a)。对于上述例子，我们得到x¹⁰系数的值为3，正是由于AP（2,5,8）。（这些系数x^2b始终为奇数，由于上述原因。而q中的所有其他系数始终为偶数。）

那么，算法是查看这些项x^2b的系数，并查看它们是否大于1。如果没有，则没有均匀间隔的1。如果在L中存在一个b，使得x^2b的系数大于1，则我们知道除(b,b)之外还有一些配对(a,c)满足a+c=2b。要找到实际的配对，我们只需尝试L中的每个a（相应的c将为2b-a），并查看S中位置2b-a是否有1。此步骤的时间复杂度为O(n)。

就这些了，伙计们。

有人可能会问：我们需要使用FFT吗？许多答案，例如beta的，flybywire的和rsp的，建议采用检查每对1并查看第三个位置是否有1的方法，可以在O(n log n)内运行，因为如果有太多的1，我们会很容易地找到三元组，如果有太少的1，则检查所有对需要很少时间。不幸的是，尽管这种直觉是正确的，而且简单的方法比O(n²)更好，但它并没有显著提高。就像sdcvvc的答案一样，我们可以采用长度为n=3^k的字符串的“类似康托尔集”的方法，在其中只有0和2（没有1）的三进制表示中具有1的位置。这样的字符串中有2^k=n^(log 2)/(log 3)≈n^0.63个1，并且没有均匀间隔的1，因此检查所有对的数量将与其中的1的平方数同阶：即4^k≈n^1.26，这比（n log n）大得多。事实上，最坏情况甚至更糟：Leo Moser在1953年构造（有效地）这样的字符串，其中有n^(1-c/√(log n))个1，但没有均匀间隔的1，这意味着在这样的字符串上，简单的方法将需要Θ(n^(2-2c/√(log n)))，令人惊讶的是，这只比Θ(n^2)好了一点点！

关于长度为n的字符串中不包含3个等间距的1的最大数量（我们在上面看到至少从简单的类似Cantor的构造中为n^0.63，从Moser的构造中至少为n^{1-c/√(log n)}），这是OEIS A003002。它也可以直接从OEIS A065825计算，作为满足A065825(k) ≤ n < A065825(k+1)的k。我编写了一个程序来查找这些内容，结果发现贪心算法并不能给出最长的这样的字符串。例如，对于n=9，我们可以得到5个1（110100011），但贪心算法只给出4个（110110000）；对于n=26，我们可以得到11个1（11001010001000010110001101），但贪心算法只给出8个（11011000011011000000000000）；对于n=74，我们可以得到22个1（11000010110001000001011010001000000000000000010001011010000010001101000011），但贪心算法只给出16个（11011000011011000000000000011011000011011000000000000000000000000000000）。尽管如OEIS参考所说，它们在许多地方都达成了一致，直到50（例如所有38到50），但它们并不一致。正如OEIS参考所说，Jaroslaw Wroblewski对这个问题很感兴趣，并且他维护了一个关于这些non-averaging sets的网站。确切的数字仅已知到194。