logo标签列表

如何减少遍历字符串的时间复杂度？

cstringalgorithmsearchtime-complexity
4

我正在解决一个问题，要找到字符串 s 中大小为 n 的仅由小写字母组成的字符串，其中索引位置a, b, c, d 满足以下条件：

1 <= a < b < c < d <= n

并且

s[a] == s[c] and s[b] == s[d]

我编写的代码以基本方式逐个字符遍历该字符串：

#include<stdio.h>

int main()
{
    int n, count = 0;
    char s[2002];
    scanf("%d%s", &n, s);
    for(int a = 0; a<n-3; a++)
    {
        for(int b = a + 1; b<n-2; b++)
        {
            for(int c = b + 1; c<n-1; c++)
            {
                for(int d = c + 1; d<n; d++)
                {
                    if(s[a] == s[c] && s[b] == s[d] && a>=0 && b>a && c>b && d>c && d<n)
                    {
                        count++;
                    }
                }
            }
        }
    }
    printf("%d", count);
    return 0;
}

a、b、c和d是索引。问题在于，如果输入字符串很大，则由于4个嵌套循环而超出时间限制。是否有任何方法可以改进代码以减少复杂性？

问题陈述在这里：https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/algorithm/holiday-season-ab957deb/

在O（n）的时间复杂度内解决这个问题会很困难。然而，使用O（n ^ 2）是可能的。 - AKSingh
尽管问题描述有意地掩盖了它，但这是一个重叠区间问题。 - John Bollinger
我成功解决了你的问题。我的代码复杂度为O(n^2)。 - AKSingh
6个回答
3

如果您维护一个数组，该数组存储输入字符串中每个字符的累积频率（频率分布中频率和到目前为止所有频率的总和），则可以解决此问题。由于字符串只包含小写字符，因此数组大小将为[26][N+1]。

例如：

index  - 1 2 3 4 5
string - a b a b a

cumulativeFrequency array:

    0  1  2  3  4  5
a   0  1  1  2  2  3
b   0  0  1  1  2  2

我通过将输入字符串的第一个字符的索引设置为1来创建了该数组。这样做将有助于我们稍后解决问题。现在，只需忽略列0，并假设字符串从索引1而不是0开始。

有用的信息

使用累积频率数组，我们可以轻松地检查一个字符是否存在于任何索引i处：

if cumulativeFrequency[i]-cumulativeFrequency[i-1] > 0
从i到j范围内（不包括i和j）字符出现的次数： 
frequency between i and j =  cumulativeFrequency[j-1] - cumulativeFrequency[i]

算法

1: for each character from a-z:
2:     Locate index a and c such that charAt[a] == charAt[c]
3:     for each pair (a, c):
4:         for character from a-z:
5:             b = frequency of character between a and c
6:             d = frequency of character after c
7:             count += b*d

时间复杂度

第1-2行:

最外层循环将运行26次。我们需要找到所有的(a, c)组合，为此我们需要O(n^2)的时间复杂度。

第3-4行:

对于每个组合，我们再次运行一个循环26次，以检查在a和c之间以及c之后每个字符出现的次数。

第5-7行:

使用累积频率数组，对于每个字符，我们可以在O(1)的时间内轻松计算它在a和c之间以及c之后出现的次数。

因此，总体复杂度为 O(26*n^2*26) = O(n^2)。

代码

我用Java编写代码。我没有C语言的代码。我使用了简单的循环和数组，因此应该很容易理解。

//Input N and string 
//Do not pay attention to the next two lines since they are basically taking 
//input using Java input streams
int N = Integer.parseInt(bufferedReader.readLine().trim());
String str = bufferedReader.readLine().trim();

//Construct an array to store cumulative frequency of each character in the string
int[][] cumulativeFrequency = new int[26][N+1];

//Fill the cumulative frequency array
for (int i = 0;i < str.length();i++)
{
    //character an index i
    char ch = str.charAt(i);

    //Fill the cumulative frequency array for each character 
    for (int j = 0;j < 26;j++)
    {
        cumulativeFrequency[j][i+1] += cumulativeFrequency[j][i];
        if (ch-97 == j) cumulativeFrequency[j][i+1]++;
    }
}

int a, b, c, d;
long count = 0;

//Follow the steps of the algorithm here
for (int i = 0;i < 26;i++)
{
    for (int j = 1; j <= N - 2; j++)
    {
        //Check if character at i is present at index j
        a = cumulativeFrequency[i][j] - cumulativeFrequency[i][j - 1];

        if (a > 0)
        {
            //Check if character at i is present at index k
            for (int k = j + 2; k <= N; k++)
            {
                c = cumulativeFrequency[i][k] - cumulativeFrequency[i][k - 1];

                if (c > 0)
                {
                    //For each character, find b*d
                    for (int l = 0; l < 26; l++)
                    {
                        //For each character calculate b and d
                        b = cumulativeFrequency[l][k-1] - cumulativeFrequency[l][j];
                        d = cumulativeFrequency[l][N] - cumulativeFrequency[l][k];

                        count += b * d;
                        }
                    }
                }
            }
        }
    }

    System.out.println(count);

我希望我已经对你有所帮助。我提供的代码不会引起时间复杂度错误，并且它将适用于所有测试案例。如果我的解释有什么你不明白的地方，请在评论区留言。

这是一个很好的方法。考虑到我写了一个完全没有代码的答案（因为我认为问题的提出者应该自己编写代码），我实在无法因为在一个C语言问题中提供了Java代码而指责它。 - John Bollinger
@JohnBollinger 感谢您的反馈。我只是在Java代码中编写了简单的循环。如果任何人真的想知道代码如何工作，他们仍然需要使用笔和纸哈哈。 - AKSingh
1

在早期阶段进行相等性检查可以节省一些时间。 此外，检查a>=0 && b>a && c>b && d>c && d<n似乎是不必要的，因为你已经在循环中检查了这个条件。改进后的版本如下：

#include<stdio.h>

int main()
{
    int n, count = 0;
    char s[2002];
    scanf("%d%s", &n, s);
    for(int a = 0; a<n-3; a++)
    {
        for(int b = a + 1; b<n-2; b++)
        {
            for(int c = b + 1; c<n-1; c++)
            {
                if(s[a] == s[c]) {
                    for(int d = c + 1; d<n; d++)
                    {
                        if(s[b] == s[d])
                        {
                            count++;
                        }
                    }
                }
            }
        }
    }
    printf("%d", count);
    return 0;
}
谢谢，修改确实解决了更多的测试用例，而且在时间限制内，但仍有一些情况超过限制，虽然只是一点点。是否有任何方法可以合并任意两个循环？ - rohan843
1
在最坏的情况下，整个字符串都包含相同的字符，此时每个满足 1 <= a < b < c < d <= N 的索引都会满足 s[a] == s[c] && s[b] == s[d]，因此计数器将增加到 n*(n-1)*(n-2)*(n-3) / 4!，即 O(n^4)。换句话说，假设计数过程是逐一进行的（使用 counter++），没有办法使最坏情况的时间复杂度优于 O(n^4)。
话虽如此，这个算法可以被改进。一种可能且非常重要的改进是，如果 s[a] != s[c]，那么继续检查所有可能的索引 b 和 d 就没有意义了。用户3777427走了这个方向，它可以进一步改进如下：
for(int a = 0; a < n-3; a++)
{
    for(int c = a + 2; c < n-1; c++)
    {
        if(s[a] == s[c])
        {
            for(int b = a + 1; b < c; b++)
            {
                for(int d = c + 1; d < n; d++)
                {
                    if(s[b] == s[d])
                    {
                        count++;
                    }
                }
            }
        }
    }
}

编辑：

经过一些思考，我找到了一种方法将最坏时间复杂度降低到O(n^3)，即使用直方图。

首先，我们遍历字符数组一次，并填充直方图，使得直方图中的索引'a'包含'a'出现的次数，索引'b'包含'b'出现的次数，以此类推。

然后，我们使用直方图来消除最内部循环（d循环）的需要，就像这样：

int histogram1[256] = {0};
for (int i = 0; i < n; ++i)
{
    ++histogram1[(int) s[i]];
}

int histogram2[256];

for(int a = 0; a < n-3; a++)
{
    --histogram1[(int) s[a]];
    
    for (int i = 'a'; i <= 'z'; ++i)
    {
        histogram2[i] = histogram1[i];
    }

    --histogram2[(int) s[a+1]];

    for (int c = a + 2; c < n-1; c++)
    {
        --histogram2[(int) s[c]];

        for (int b = a + 1; b < c; b++)
        {
            if (s[a] == s[c])
            {
                count += histogram2[(int) s[b]];
            }
        }
    }
}
谢谢，改进在指定时间内解决了更多的测试用例，但时间限制问题仍然存在，但改变逻辑流程的建议非常有用。 - rohan843
@rohan843 我编辑并添加了一个改善的解决方案。 - Orielno
@rohan843 我之前的改进方案有一个错误，现在我已经进行了编辑，并放入了一段代码，我已经测试并确保其正确运行。 - Orielno
1
由于字符串S仅由小写字母组成，因此您可以维护一个26x26的表格（实际上是25x25，当i=j时忽略），该表格保存所有可能的不同两个字母情况的出现次数（例如ab，ac，bc等）。
以下代码通过两个函数跟踪每个答案候选项（abab，acac，bcbc等）的完整性：检查AC位置和检查BD位置。一旦值达到4，就意味着该候选项是一个有效答案。
#include <stdio.h>

int digitsAC(int a)
{
    if(a % 2 == 0)
        return a + 1;
    return a;
}

int digitsBD(int b)
{
    if(b % 2 == 1)
        return b + 1;
    return b;
}

int main()
{
    int n, count = 0;
    char s[2002];
    int appearance2x2[26][26] = {0};
    scanf("%d%s", &n, s);
    for(int i = 0; i < n; ++i)
    {
        int id = s[i] - 'a';
        for(int j = 0; j < 26; ++j)
        {
            appearance2x2[id][j] = digitsAC(appearance2x2[id][j]);
            appearance2x2[j][id] = digitsBD(appearance2x2[j][id]);  
        }
    }
    //counting the results
    for(int i = 0; i < 26; ++i)
    {
        for(int j = 0; j < 26; ++j)
        {
            if(i == j)continue;
            if(appearance2x2[i][j] >= 4)count += ((appearance2x2[i][j] - 2) / 2);
        }
    }
    printf("%d", count);
    return 0;
}

时间复杂度为O(26N)，相当于线性。 可以通过进行位掩码操作进一步加速代码，但我将函数保持简单以便易懂。 没有经过大量测试，请在发现任何错误时告诉我！ 编辑：处理连续出现的字母（如aabbaabb）存在问题。
使用辅助数组的想法不错，但是这段代码与原始代码（以及问题所要求的）不同，我认为：您计算了可能的字母组合，但是原始代码计算了从字符串中可能的“选择”，其中“ababababa”应该具有超过两个命中。 - M Oehm
哇，看起来我误解了问题。但我感觉在计数部分进行微调应该可以解决问题。我会在运行几个测试用例后编辑我的答案。 - Sorevan
1
该程序无法处理输入字符串 ababab。计数应为 6，而输出结果为 3。 - AKSingh
1
这里有一个O（n）的解决方案（允许字符集中的字符数量为常量）。
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>


/*  As used in this program, "substring" means a string that can be formed by
    characters from another string.  The resulting characters are not
    necessarily consecutive in the original string.  For example, "ab" is a
    substring of "xaxxxxbxx".

    This program requires the lowercase letters to have consecutive codes, as
    in ASCII.
*/


#define Max   2000      //  Maximum string length supported.
typedef short     T1;   //  A type that can hold Max.
typedef int       T2;   //  A type that can hold Max**2.
typedef long      T3;   //  A type that can hold Max**3.
typedef long long T4;   //  A type that can hold Max**4.
#define PRIT4 "lld"     //  A conversion specification that will print a T4.

#define L   ('z'-'a'+1) //  Number of characters in the set allowed.


/*  A Positions structure records all positions of a character in the string.
    N is the number of appearances, and Position[i] is the position (index into
    the string) of the i-th appearance, in ascending order.
*/
typedef struct { T1 N, Position[Max]; } Positions;


/*  Return the number of substrings "aaaa" that can be formed from "a"
    characters in the positions indicated by A.
*/
static T4 Count1(const Positions *A)
{
    T4 N = A->N;
    return N * (N-1) * (N-2) * (N-3) / (4*3*2*1);
}


/*  Return the number of substrings "abab" that can be formed from "a"
    characters in the positions indicated by A and "b" characters in the
    positions indicated by B.  A and B must be different.
*/
static T4 Count2(const Positions *A, const Positions *B)
{
    //  Exit early for trivial cases.
    if (A->N < 2 || B->N < 2)
        return 0;

    /*  Sum[i] will record the number of "ab" substrings that can be formed
        with a "b" at the position in B->Position[b] or earlier.
    */
    T2 Sum[Max];

    T3 RunningSum = 0;

    /*  Iterate b through the indices of B->Position.  While doing this, a is
        synchronized to index to a corresponding place in A->Position.
    */
    for (T1 a = 0, b = 0; b < B->N; ++b)
    {
        /*  Advance a to index into A->Position where where A->Position[i]
            first exceeds B->Position[b], or to the end if there is no such
            spot.
        */
        while (a < A->N && A->Position[a] < B->Position[b])
            ++a;

        /*  The number of substrings "ab" that can be formed using the "b" at
            position B->Position[b] is a, the number of "a" preceding it.
            Adding this to RunningSum produces the number of substrings "ab"
            that can be formed using this "b" or an earlier one.
        */
        RunningSum += a;

        //  Record that.
        Sum[b] = RunningSum;
    }

    RunningSum = 0;

    /*  Iterate a through the indices of A->Position.  While doing this, b is
        synchronized to index to a corresponding place in B->Position.
    */
    for (T1 a = 0, b = 0; a < A->N; ++a)
    {
        /*  Advance b to index into B->Position where where B->Position[i]
            first exceeds A->Position[a], or to the end if there is no such
            spot.
        */
        while (b < B->N && B->Position[b] < A->Position[a])
            ++b;

        /*  The number of substrings "abab" that can be formed using the "a"
            at A->Position[a] as the second "a" in the substring is the number
            of "ab" substrings that can be formed with a "b" before the this
            "a" multiplied by the number of "b" after this "a".

            That number of "ab" substrings is in Sum[b-1], if 0 < b.  If b is
            zero, there are no "b" before this "a", so the number is zero.

            The number of "b" after this "a" is B->N - b.
        */
        if (0 < b) RunningSum += (T3) Sum[b-1] * (B->N - b);
    }

    return RunningSum;
}


int main(void)
{
    //  Get the string length.
    size_t length;
    if (1 != scanf("%zu", &length))
    {
        fprintf(stderr, "Error, expected length in standard input.\n");
        exit(EXIT_FAILURE);
    }

    //  Skip blanks.
    int c;
    do
        c = getchar();
    while (c != EOF && isspace(c));
    ungetc(c, stdin);

    /*  Create an array of Positions, one element for each character in the
        allowed set.
    */
    Positions P[L] = {{0}};

    for (size_t i = 0; i < length; ++i)
    {
        c = getchar();
        if (!islower(c))
        {
            fprintf(stderr,
"Error, malformed input, expected only lowercase letters in the string.\n");
            exit(EXIT_FAILURE);
        }
        c -= 'a';
        P[c].Position[P[c].N++] = i;
    }

    /*  Count the specified substrings.  i and j are iterated through the
        indices of the allowed characters.  For each pair different i and j, we
        count the number of specified substrings that can be performed using
        the character of index i as "a" and the character of index j as "b" as
        described in Count2.  For each pair where i and j are identical, we
        count the number of specified substrings that can be formed using the
        character of index i alone.
    */
    T4 Sum = 0;
    for (size_t i = 0; i < L; ++i)
        for (size_t j = 0; j < L; ++j)
            Sum += i == j
                ? Count1(&P[i])
                : Count2(&P[i], &P[j]);

    printf("%" PRIT4 "\n", Sum);
}
0

问题

对于这个问题，认识到它是一个重叠区间计数的练习可能会有所帮助。例如，如果我们将输入中相同字符的每一对视为半开区间的端点，则问题是要求计算重叠的区间对的数量，而不是一个子集。

算法

解决这个问题的一种方法是首先识别和记录所有区间。可以通过使用两层循环嵌套对输入进行简单扫描来轻松实现这一点，并以左端点分组并按右端点在每个组内排序。

这样组织区间既方便减少重叠搜索空间，也更有效地计数。特别是，可以像这样处理计数：

对于每个区间I，考虑左端点严格在I的端点之间的区间组。 在考虑的每个组内，执行二分搜索以查找右端点比I的右端点大1的区间，或者该区间将出现的位置。 从该点到结尾的该组的所有成员都满足重叠条件，因此将该数字添加到总计数中。

复杂度分析

排序后的区间列表和组大小/边界可以通过两级循环嵌套以O(n2)的代价创建。总共可能有多达n * (n - 1)个区间，当所有输入字符相同时发生，因此列表需要O(n2)的存储空间。

时间段被分成恰好 n-1 组，其中一些可能为空。对于每个时间段（O(n2)），我们考虑其中最多 n-2 个，并在每个上执行二分查找（O(log n)）。这将产生 O(n3 log n) 的总操作次数。
与您原始算法的 O(n4) 成本相比，这是一种算法改进，但尚不清楚改进的渐近复杂度是否对正在测试的特定问题大小表现出改进的性能。
你链接到一个网页，上面说有一个O(n log n)的解决方案，但你展示了一个O(n^3 log n)的算法？此外，那个网页有一个O(n log n)的解决方案，因为它需要先对区间进行排序。我们得到一个带有标记间隔的字符串（每个字符在其位置上开始和结束潜在的间隔），所以我们不需要排序。有一个O(n)的解决方案（在实际复杂度中，将字长乘法等计算作单步）。 - Eric Postpischil
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接