what would happen of the input is like this : 5, 5, 66, 66, 7, 1, 1, 77,7 i think in this case the moment window reaches to point (66,7,1) it will take 7 as unique number but that too window will not move any futhur , but 7 is not unique .
Please comment if i misunderstood ur explanation . On Wed, Feb 6, 2013 at 11:31 PM, Srikar <[email protected]> wrote: > *APPROACH 1:* > use a hashtable for both the questions ? > > Insert the integers as they are given in the array into a hashtable. The > structure I am thinking is key (the integer) -> [index]. Once all elements > are inserted. Run through the hashtable and select the one which has > len(value) == 1 and is least, since we want the first unique integer. > > for the second Q, its a more general Q of the first one. In first k=1. > > space: 2O(n) > time: 2O(n) > > *APPROACH2: * > When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, > 77]. In this lets have moving window of 3. first consider (5,5,66). we can > easily estab. that there is duplicate here. So move the window by 1 element > so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. > next (66,7,1). No dups here! take the middle element as this has to be the > first unique in the set. The left element belongs to the dup so could 1. > Hence 7 is the first unique element. > > space: O(1) > time: O(n) > > For seond Q I still think hashtable is best. As the numbers are streamed, > keep inserting. > > > Srikar > > > > 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. >> >> >> > -- > 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. > > > -- 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.
