hey guys why hashing? can't we simply sort the array of characters in-place - space complexity O(1) . and then simply rearrange the array in-place with character+frequency.
On Sun, Sep 4, 2011 at 3:13 PM, bharatkumar bagana < bagana.bharatku...@gmail.com> wrote: > +1 rahul and +1 ankuj > > > On Sat, Sep 3, 2011 at 11:37 AM, icy` <vipe...@gmail.com> wrote: > >> Just use a hash to count frequency of something; e.g. in ruby: >> ar= %w(a a b c a b b c d e a d e f) >> freq=Hash.new(0) >> ar.each {|c| freq[c]+=1} >> p freq >> >> #output >> #{"a"=>4, "b"=>3, "c"=>2, "d"=>2, "e"=>2, "f"=>1} >> >> you could only do it in place in O(1) only if your input array is >> already 2*(number of all possible characters) size, but you didnt >> mention size of input array. For example, what if input was just >> [a,b,c,d,e] ? The size is 5. You cant just convert the input >> into [a,1,b,1,c,1,d,1,e,1] without increasing the size to 10. So >> hash is the better method. >> >> On Sep 3, 11:04 am, Ankuj Gupta <ankuj2...@gmail.com> wrote: >> > if for all inputs you array remains of same size we can take it as >> > constant space >> > >> > On Sep 3, 7:49 pm, rajul jain <rajuljain...@gmail.com> wrote: >> > >> > >> > >> > >> > >> > >> > >> > > @ankuj just want to clarify that in hashing method we require array >> of >> > > fixed size let say arr[26] , so is it considered as constant space or >> not? >> > >> > > On Sat, Sep 3, 2011 at 8:02 PM, siddharam suresh < >> siddharam....@gmail.com>wrote: >> > >> > > > sol already posted please search old thread >> > > > Thank you, >> > > > Sid. >> > >> > > > On Sat, Sep 3, 2011 at 8:01 PM, Ankuj Gupta <ankuj2...@gmail.com> >> wrote: >> > >> > > >> If we take our input to be characters a-z ans A-Z then we require >> > > >> fixed space which can be treated as O(1). >> > > >> On Sep 3, 7:10 pm, teja bala <pawanjalsa.t...@gmail.com> wrote: >> > > >> > this 'll work if u i/p the string in dis manner >> > > >> > aaabbcc(consecutive same) >> > > >> > a3b2c2 >> > >> > > >> > #include<stdio.h> >> > > >> > #include<conio.h> >> > > >> > main() >> > > >> > { >> > > >> > int x=1,i=0; >> > > >> > char a[100]; >> > > >> > gets(a); >> > > >> > while(a[i]!='\0') >> > > >> > { >> > > >> > while(a[i]==a[i+1]) >> > > >> > { >> > > >> > x++; >> > > >> > i++; >> > > >> > } >> > > >> > printf("%c%d",a[i],x); >> > > >> > x=1; >> > > >> > i++; >> > > >> > } >> > > >> > getchar(); >> > >> > > >> > } >> > >> > > >> -- >> > > >> You received this message because you are subscribed to the Google >> Groups >> > > >> "Algorithm Geeks" group. >> > > >> To post to this group, send email to algogeeks@googlegroups.com. >> > > >> To unsubscribe from this group, send email to >> > > >> algogeeks+unsubscr...@googlegroups.com. >> > > >> For more options, visit this group at >> > > >>http://groups.google.com/group/algogeeks?hl=en. >> > >> > > > -- >> > > > You received this message because you are subscribed to the Google >> Groups >> > > > "Algorithm Geeks" group. >> > > > To post to this group, send email to algogeeks@googlegroups.com. >> > > > To unsubscribe from this group, send email to >> > > > algogeeks+unsubscr...@googlegroups.com. >> > > > For more options, visit this group at >> > > >http://groups.google.com/group/algogeeks?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > > **Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > *BharatKumar Bagana* > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> > * > Mobile +91 8056127652* > <bagana.bharatku...@gmail.com> > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- ........................ *MOHIT VERMA* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.