I guess the part 1 can be solved in O(n) time and space both. Here is my
approach.
Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6}
1. Given an array, scan thru it, element by element and hash it on a
hashmap with key as the arr[i] as the key and i+1 as the index.
2. There would be two cases
a) arr[i] is already there in the hash map, if so, check if the
hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing.
If its is not negative, negate it.
b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1
as the value.
3. Scan thru the value set, the key corresponding to minimum of positive
values is the answer.
Example.
For {2,3,1,2,3,2,4,1, 5,6}
2 = not seen, hash 2,1 (arr[i], i+1)
3 = not seen, hash 3, 2
1 = not seen, hash 1,3
2 = seen -> is the value corresponding to key 2 negative = No. So negate
it- hash entry now becomes 2,-1
3 = similar to above -> Hash entry is 3,-2
2 = seen, is the value negative = yes, do nothing
4 = not seen, hash 4,8
1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry
= 1,-3
5 = not seen, hash 5,10
6= not seen, hash 6,11
Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11
Whats the *least minimum of positive values*? 8
Whats the key corresponding to value 8? Its 4.
*4 is the first unique number!*
Please let me know if you need the code, shall send you ova :)
Cheers,
*Pralay*
*MS,Comp Sci, *
*University of California, Irvine*
On Tue, Feb 5, 2013 at 8:30 PM, 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.
