Re: [algogeeks] Duplicates in a string
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 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 > 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 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.
Re: [algogeeks] Duplicates in a string
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 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 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.
Re: [algogeeks] Duplicates in a string
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 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.
Re: [algogeeks] Duplicates in a string
We can do it in just one pass. Start scanning the array and whichever element gets scanned just store some kind of marker in the additional array that this element has been vsisted.Next time you get some element if that element (or character) is not visited earlier than mark it as visited and print it or if it was visited earlier just skip it. On Fri, Aug 5, 2011 at 8:30 PM, nishaanth wrote: > Store the frequency of all the letters in an array in one scan(like > counting sort). In the next pass remove the duplicates and appropriately > shift . takes 2 O(n) passes i guess > > > On Fri, Aug 5, 2011 at 4:50 PM, priya v wrote: > >> >> Remove duplicate alphabets from a string and compress it in the same >> string. For >> example, MISSISSIPPI becomes MISP. O (n2) is not acceptable. >> For this problem is it a good idea to sort the array using a sorting >> technique with efficiency O(nlogn) >> and remove the duplicates? >> >> -- >> 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. >> > > > > -- > S.Nishaanth, > Computer Science and engineering, > IIT Madras. > > -- > 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.
Re: [algogeeks] Duplicates in a string
Store the frequency of all the letters in an array in one scan(like counting sort). In the next pass remove the duplicates and appropriately shift . takes 2 O(n) passes i guess On Fri, Aug 5, 2011 at 4:50 PM, priya v wrote: > > Remove duplicate alphabets from a string and compress it in the same > string. For > example, MISSISSIPPI becomes MISP. O (n2) is not acceptable. > For this problem is it a good idea to sort the array using a sorting > technique with efficiency O(nlogn) > and remove the duplicates? > > -- > 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. > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.
[algogeeks] Duplicates in a string
Remove duplicate alphabets from a string and compress it in the same string. For example, MISSISSIPPI becomes MISP. O (n2) is not acceptable. For this problem is it a good idea to sort the array using a sorting technique with efficiency O(nlogn) and remove the duplicates? -- 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.
