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 - C中fgets函数的字符串长度

c - 为什么空数组的字符串长度与数组大小不同?

C 编程 - strlen 的功能

c++ - 什么时候调用_findclose?

c - getaddrinfo 似乎在 Windows 和 Ubuntu 之间返回不同的结果?

c++ - 如何正确声明和初始化一个字符数组?

c++ - 空指针 C++ 的段错误

c - 发送:无效参数

c - C中的静态和外部有什么区别?

c++ - 应用程序段错误,仅当使用 MinGW 在 Windows 上编译时