c - 使用 strlen() 时超出时间限制错误?

标签 c segmentation-fault strlen time-limiting

<分区>

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

#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;
}

问题出在哪里?

最佳答案

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

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

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

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

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

这里,O(n^2) 是一个非常大的计算量。

关于c - 使用 strlen() 时超出时间限制错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31148844/

相关文章:

c - 评论 2 免费时出现段错误(推箱子游戏)

python - Tkinter 导致 SIGSEGV 和系统崩溃 - 如何修复?

c - CMX ColdFire USB-Lite 堆栈的文档

c - 链接时间 "undefined reference to "错误

c++ - 如何启动我的简单 hello world 程序?

c - printf %s 段错误 - 为什么?

php - 检查 php get 变量是否设置为任何值?

c - strlen(&string[]) 是如何工作的?

c - 当我在我的计算机和学校计算机上编译时,消息不一样

c - 静态变量的初始化