时间戳

首页 > 解决方案 > CODEVITA“相似字符”如何降低我在c中的时间复杂度？

c - CODEVITA“相似字符”如何降低我在c中的时间复杂度？

问题描述

示例 1

输入

9

算盘

2

9

3

输出

3

1

解释

这里 Q = 2

对于 P=9，第 9 个位置的字符是“a”。'a' 在 P 之前出现的次数，即 9 是 3。

同样对于 P=3，第 3 个字符是“a”。在 P 之前出现“a”的次数，即 3 为 1。

我的回答是

#include<stdio.h>
#include<stdlib.h>

int occ(int a,char *p){
  int cnt=0;
  for(int i=0;i<a;i++){
    if(p[i]==p[a]){
      cnt++;
    }
  }

  return cnt;
}

int main(){
  int l,q;

  scanf("%d",&l);
  char s[l];
  scanf("\n%s\n%d",s,&q);
  while(q>0){
    int n;
    scanf("\n%d",&n);
    n=n-1;
    int r=occ(n,s);
    printf("%d\n",r);
    q--;
  }
}

标签： calgorithmtime-complexity

解决方案

我不是 C 专家，但我可以在这里告诉你如何提高时间复杂度。

您可以使用某种记忆，首先问：我可以从仅迭代一次数组中获得任何有用的信息，以便我可以更快地回答每个查询吗？

现在您的解决方案不预处理任何东西，并且您的复杂性是每个查询的 O(n)。让我们让它变得更好，让我们在 O(n) 中预处理数据并在 O(1) 中回答每个查询。

您将有一个字符映射，可以计算一个字符出现的次数。请注意，对于索引 i，您只需考虑 s[i] 之前的出现，因此索引 i 不关心其他字符。

遵循这种方法

  1. 创建一个大小为 s.length 的向量（int）v。
  2. 创建一个 map(char to int) m 用于计算字符出现次数。

  3. 对于 i = 0 直到 s.length 执行：

     v[i] = m[s[i]]++

这样，您只需在一次迭代中计算每个索引的答案。

现在，对于每个查询 q，只需打印 v[q - 1]。

每个查询的时间复杂度：O(1)

额外空间复杂度：O(n)

注意：为了更好地理解整个答案，n 是字符串的长度（s.length）

希望有帮助:)

推荐阅读