文字列中の最初の一意の文字を見つけるのにこのCプログラムが遅すぎるのはなぜですか？

Question

私はCが新しくなったので、私はleetcodeを通して学びたいと思っています。

https://leetcode.com/problems/first-unique-character-in-a-string/

これは質問の文字列が与えられ

、それに最初の非繰り返し文字を見つけて、それがインデックスのリターンです。存在しない場合は-1を返します。

例：

S = "leetcode" リターン0

S = "loveleetcode"、 リターン2.

そして、これは私のコード

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

int firstUniqChar(char* s) { 
    int c = 0; 
    int freq[26] = {0}; 

    while (s[c] != '\0') { 
    if (s[c] >= 'a' && s[c] <= 'z') { 
     freq[s[c] - 'a']++; 
    } 
    c++; 
    } 

    int firstChar = -1; 
    for (int i = 0; i < strlen(s); i++) { 
    if (freq[s[i] - 'a'] == 1) { 
     firstChar = i; 
     break; 
    } 
    } 
    return firstChar; 
} 

Iであります時間制限を超えていると言われているので、自分のコードが正しいことを証明することはできません。だから、私のプログラムは遅すぎると思っています。どこが間違っているのか分かりませんか？

Answer 1

strlen(s)がO（n）時間を要し、2番目のループの各繰り返しで実行されるため、コードが誤ってO（n^2）になっています。最初のループのように、あなたが\0文字を見つけるまで繰り返すことができます：正確さに

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

を：彼らは範囲a-zであるが、あなたの第二のループがない場合は、あなたの最初のループは、文字のみをカウントします。これは、最初のループでチェックが冗長であるか、または2番目のループが間違っていることを意味します（範囲a-zの文字がsにない場合は、freqが範囲外にアクセスするため）。