for 2nd question you can make a heap with their index as a factor to heapify them. whenever a integer in stream gets repeated you just nead to remove it from heap and heapify it.
On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur < [email protected]> wrote: > nice algo ankit, so it will be nlogn using O (n) space only. What abt > 2nd Q., which have a big online stream. > > On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit <[email protected]> wrote: > > For 1: > > i think you can use sorting, sort the array and keep the indices of the > > numbers in the sorted list. > > Now traverse the sorted list and in the sorted list you need to find the > > unique number with the > > minimum index which is easy to find. > > > > Eg: Array: 5 3 1 2 4 1 4 > > Indices: 0 1 2 3 4 5 6 > > > > > > After sorting : Array: 1 1 2 3 4 4 5 > > Indices: 2 5 3 1 4 6 1 > > > > Now you can see the unique number with lowest index is 3(index=1). So , > you > > have your answer. > > > > > > On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur > > <[email protected]> wrote: > >> > >> 1. Given a array,find a first unique integer. > >> 2. Integers are coming as online stream,have to find a kth unique > integer > >> till now. > >> > >> For 1. > >> > >> Even we cannot use sorting for solving this as if we sort it than our > >> first number which is non-repetitive changes. > >> > >> The best I am able to do is nlogn using a space of O( n ). > >> > >> For 2. No idea > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To unsubscribe from this group and stop receiving emails from it, send > an > >> email to [email protected]. > >> For more options, visit https://groups.google.com/groups/opt_out. > >> > >> > > > > > > > > > > -- > > Kumar Ankit > > Senior Undergraduate > > Department of Computer Engineering > > Institute of Technology > > Banaras Hindu University > > Varanasi > > Ph: +91 9473629892 > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to [email protected]. > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > > > > -- > navneet singh gaur > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
