c - 重复字符删除 - 从 O(n^2) 到 O(n)

Question

用于从给定字符串中删除重复字符的 C 程序。它使用 O(n2) 我们可以按 O(n) 的顺序来做吗？请对此程序发表评论。

int main()
{

 char a[100],b[100],temp='\0';

  int i,n,j,count=0,p=0,k=0;

 printf("ENTRE THE STRING \n");

 scanf("%s",a);

 n = strlen(a);

 i=0;

 while(i < n)
 {

   count=0;

    temp = a[i];

   for(j = i  ; j  < n ; j++ )
    {

      if(temp==a[j])
       {
         count++;
       }
   }

  if(count<2) 
   {

     b[k] = temp;

     k++;
   } 

   i++;

 }

 b[k]='\0';

 printf("THE RESULTED STRING IS \n");

 for(p = 0 ; p < k ; p++)

 printf("%c ",b[p]);

 printf("\n");

 return 0;

}

Answer 1

您可以为此创建一个O(n) 算法。

步骤:

1. 创建另一个大小为 255 的数组 bucket[]。(应调整所有字符)
2. 将 bucket[] 中的每个元素初始化为 0。
3. 运行一个循环并在索引 a[i] 处递增 bucket[]。
4. 现在，通过 bucket[] 运行另一个循环，如果 bucket[i] > 0，将 (char) i 附加到b[] 数组。

代码:

#include <stdio.h>
#include <string.h>
int main()
{
    char a[100], b[100];
    int bucket[256] = {0};
    int i;
    printf("Enter the string:");
    scanf("%s",a);
    int n = strlen(a);
    for(i = 0; i < n; ++i)
    {
        //Incrementing the character count of each character.
        bucket[a[i]]++;
    }
    //Keep track of the index where the next character is to be appended.
    int b_pos = 0;
    for (i = 0; i < 256; ++i)
    {
        //Character occurs in a[], we don't care if it occurs once 
        //or twice, we just need one instance of it.
        if (bucket[i] > 0)
        {
            b[b_pos] = (char) i;
            b_pos++;
        }
    }
    b[b_pos] = '\0';
    printf("Modified string : %s",b);
}