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

Question

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

int main()
{

 char a[100],b[100],temp='[=10=]';

  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]='[=10=]';

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

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

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

 printf("\n");

 return 0;

}

Answer 1

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

步骤：

创建另一个大小为 255 的数组 bucket[]。（应调整所有字符）
将bucket[]中的每个元素初始化为0。
运行循环并在索引 a[i].

bucket[]

现在，运行通过 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] = '[=10=]';
    printf("Modified string : %s",b);
}

Answer 2

看看这个：

int main()
{

 char a[100],b[100];

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

 printf("ENTRE THE STRING \n");

 scanf("%s",a);

 n = strlen(a);

b[0] = a[0];
k = 1;
for(i=1;i<n;i++)
{
    for(j=0;j<i;j++)
    {
        if(a[i] == b[j])
        {
            count = 1;
            break;
        }
    }
    if(count == 0)
    {
        b[k] = a[i];
        k++;
    }
    else
    {
        count = 0;
    }

}
b[k] = 0;

printf("RESULT %s",b);

return 0;
}

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

Duplicate Characters Removal - From O(n^2) to O(n)

c

time-complexity