使用 strlen() 时超出时间限制错误？

Question

以下代码按预期工作，此代码打印字符串中出现次数最多的字符：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    long int i,a[26]={0},m=0 ,c=0 ;
    char s[1000001] ;
    scanf("%s",s);
    for (i=0;s[i]!='[=10=]';i++){
        a[s[i]-'a']++;
    }
    for ( i=0 ; i<26 ; i++)
        {
            if ( a[i] > m ) {       
            m = a[i] ;
            c = i ;
            }
        }

    printf("%c",'a' + c);
    return 0;
}

但是当我使用strlen()时它会导致时间限制错误：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    long int i,a[26]={0},m=0 ,c=0 ;
    char s[1000001] ;
    scanf("%s",s);
    for (i=0;i<strlen(s);i++){
        a[s[i]-'a']++;
    }
    for ( i=0 ; i<26 ; i++)
        {
            if ( a[i] > m ) {       
            m = a[i] ;
            c = i ;
            }
        }

    printf("%c",'a' + c);
    return 0;
}

问题出在哪里？

Answer 1

char s[1000001]

根据 OS，这对于堆栈来说可能太大了。您应该使用 malloc() 或在文件范围内动态分配。即使堆栈足够大，在堆栈上放置这么大的数组也不是好的做法。

除此之外：strlen() 对每个循环迭代进行评估，在字符串中搜索 NUL 终止符。对于最坏的情况（最大长度），strlen 被处理 1000000 次，搜索 s 的所有 1000001 个位置（O(n**2)）。

您应该将其分配给循环外的变量并使用它进行比较：

size_t slen = strlen(s);
for ( i = 0 ; i < slen ; i++ ) {

或者坚持第一个版本，也可以。

Answer 2

for (i=0;i<strlen(s);i++)

此代码正在调用 strlen(s) 函数。它需要 O(n) 时间复杂度。

for (i=0;s[i]!='[=11=]';i++)

此代码不调用任何函数，因此会比之前的代码快得多。

首先，在 i 的每次迭代中检查 s 的长度，并且需要 O(n) 才能找到最后一个 0，因此需要 O(n^2)，第二种情况是 O(n)。

这里O(n^2)计算量很大

使用 strlen() 时超出时间限制错误？

Time limit exceeded error when using strlen()?

c

segmentation-fault

strlen

time-limiting