By heapsort i meant : After building the min heap(or max heap) ,we extract the top of heap and put it at the end of the array constraint to one condition that if the element already exists at a[heap-size+1] then dont add just discard and continue.
O(nlogn) and inplace with no extra memory.But even i believe that 26 bits is not extra memory may be bitmask is better. On Sat, Jul 23, 2011 at 5:15 PM, Akshata Sharma <[email protected]>wrote: > @ross, I have posted my question in a new thread, not as a reply to any > existing thread!!! > > > On Sat, Jul 23, 2011 at 5:13 PM, ross <[email protected]> wrote: > >> check for visited can also be implemented by using an integer variable >> and setting corresponding bits! >> >> On Jul 23, 4:39 pm, ross <[email protected]> wrote: >> > @akshata sharma: >> > Kindly post a new question as a separate thread and not as a reply to >> > an existing one so tat it would be noticed by many ppl! >> > As akash suggestd, use a bit vector called 'visited' of 26 size for >> > ASCII or of a larger size in case of Unicode ( still constant space >> > and i dont think declaring 26 variables counts as an additional DS!!), >> > if visited then , ignore the character while processing. >> > a simple algorithm, >> > int last_ptr=0; >> > for ( i = 0 - N ) >> > { >> > if(visited(a[i])) continue; >> > else a[last_ptr++]=a[i]; >> > visited(a[i]) = true;} >> > >> > a[last_ptr]=NULL; >> > print (%s,a) ; >> > >> > On Jul 23, 12:56 pm, Akshata Sharma <[email protected]> wrote: >> > >> > >> > >> > >> > >> > >> > >> > > better than O(n^2).. >> > >> > > On Sat, Jul 23, 2011 at 1:08 PM, Akshata Sharma >> > > <[email protected]>wrote: >> > >> > > > Given a string *Str of ASCII characters, write the pseudo code to >> remove >> > > > the duplicate elements present in them. For example, if the given >> string is >> > > > "Potato", then, the output has to be "Pota". Additional constraint >> is, the >> > > > algorithm has to be in-place( no extra data structures allowed) . >> Extend >> > > > your algorithm to remove duplicates in the string which consisted of >> UNICODE >> > > > characters. >> >> -- >> 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. > -- regards, chinna. -- 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.
