RLE run length encoding is another solution because counting sort
eats space whilw with RLE we can do it in
time complexity O(n)
Space Complexity O(1)
Correct me if i am wrong ...i m talking about possibility not
exactness.
Regards
Shashank
--
You received this message because you are
@bittu ,
I think RLE , would be of no use ;
as
inp:AAABBRRGH
out :3A2B2R1G1H
so to reach the top 5 counts , there will be of no use .
as stated earlier by others ,
HASH TABLE will be the one of best solution for this .
maintain hash table in O(n) and then sort it .for top 5 counts.
Please
As you work with strings, you cannot apply count sort here.
Basic approach is to sort array, iterate over it and mantain ordered set of
5 items.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
We can apply count sort here also and take the range of numbers as
256 . Example take an array c[256] , where c[i] gives the number of
times i_th ASCII value is repeated . Then after you have obtained
c[256] . Check for maximum 5 nos. in this array (which can be done in
O(n) time and space).
--
@Decipher
As far as I understand the problem it says returns the 5 most common
occuring strings in a list, and the example u give is of a character array,
when u go to a list of strings with len_of_each_string 1, u wil have to
*hash* them, which is when u will run into problems with count sort.
From the questions example it seems they are looking for five most common
character seen in the list. Please clarify on this.
On Fri, Jan 7, 2011 at 2:02 PM, Avi Dullu avi.du...@gmail.com wrote:
@Decipher
As far as I understand the problem it says returns the 5 most common
occuring strings
Here's a different language from the usual to enjoy! This algorithm is O(n)
where n is the length of the input.
with Ada.Text_IO, Ada.Strings.Unbounded.Text_IO, Ada.Strings.Unbounded;
use Ada.Text_IO, Ada.Strings.Unbounded.Text_IO, Ada.Strings.Unbounded;
procedure Top5 is
type Pair_Type
