1

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

#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]!='\0';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;
}

问题出在哪里？

4

2 回答 2

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

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

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

这段代码不调用任何函数，所以会比前面的快得多。

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

这里，O(n^2)是一个很大的计算量。

于 2015-06-30T22:51:45.233 回答
1 
char s[1000001]

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

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

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

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

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

于 2015-06-30T22:47:50.470 回答