当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - How Can we store the frequency of alphabets in a string?

问题描述:

How can we store the frequency of alphabets in a string using minimum possible memory..

I think bit array or using bit manipulation, this cannot be achieved as we need to store the frequency, and not only the occurrence of alphabet(true or false)...

Please let me know, if any other data structure exist for this problem..

also, we need to find the alphabets which has maximum frequency (aplhabets with same maximum frequency ) should get printed.?? Please i need an efficient alogrithm...

网友答案:

I think Huffman coding is what you want, but explain your problem more to understand it better, there are some other ways, but you should explain your problem (At least I'm one of a person needs more explanation).

网友答案:

/* For a short string, like "abaz" a Hashmap like (a:2, b:1, z:1) will be shorter, than a whole alphabet*/

main()

{

  int count,i,j;
  char str[50];

  printf("Enter string : ");
  gets(str);

  for(i=0;i<=strlen(str)-1;i++)
  {
          count=1;
          if(str[i]==' ')
             continue;
          for(j=i+1;j<=strlen(str)-1;j++)
          {   
                 if(str[i]==str[j])
                 {
                        str[j]=' ';
                        count++;
                 }
          }
          printf("%c : %d \n",str[i],count);
  }                
  getch();
}                        
网友答案:

For a short string, like "abaz" a Hashmap like (a:2, b:1, z:1) will be shorter, than a whole alphabet.

Is it just for ascii a-z, or are UTF-8 characters considered?

网友答案:

Create a HashMap having the characters mapped to the frequency. Also keep a maximum count and increment it when needed. At the end, you have all the frequencies stored and the maximum count. Now iterate over the hashmap and pick the character keys which are mapped to a value equal to maximum count.

Storing = O(n) Retrieving all the characters with maximum frequency = O(n)

So, both together are done in linear time.

分享给朋友:
您可能感兴趣的文章:
随机阅读: