c - 为什么这个查找字符串中第一个唯一字符的 C 程序太慢了？

Question

我是 C 的新手。所以，我正在尝试通过 leetcode 学习。

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

这就是问题

给定一个字符串，找到其中的第一个非重复字符并返回它的索引。如果不存在，则返回-1。

例子:

s = "力扣"返回 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;
}

我无法证明我的代码是正确的，因为它说超出了时间限制。所以，我猜我的程序太慢了。不确定我哪里做错了？

Answer 1

你的代码不小心是 O(n^2) 因为 strlen(s)花费 O(n) 时间，并在第二个循环的每次迭代中执行。与第一个循环一样，您可以迭代直到找到 \0。字符:

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

关于正确性:您的第一个循环只计算在 a-z 范围内的字符但你的第二个循环没有。这意味着第一个循环中的检查是多余的，或者第二个循环是错误的(因为如果 freq 中有不在 a-z 范围内的字符，它将访问 s 超出范围)。