u can use a bool array size- 26 and do char[i]-'A' = 1 , check it to decide the first instance of the character. this can be done in O(n). u can even use bit mask to make ur code look better ( ;) )
On 8/5/11, priya v <[email protected]> wrote: > If an additional storage is used to store the frequency / marker searching > the frequency/marker in the array would require an additional nested loop. > Would it still be O(n)? > > On Fri, Aug 5, 2011 at 8:36 PM, kartik sachan > <[email protected]>wrote: > >> I think in this case count sort type thing would work better way >> >> just take a array of max 26(as 26 CHARACTER ARE THERE) >> >> and using index as count['M']=store how many times M has comes >> >> similary store other character >> >> now print array whose value >0 >> >> but IN this case u might lost the ORDER......................(but that can >> be done using binary search using T(log(n)) >> >> >> the total time complexcity is O(n) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
