On Feb 3, 2008 10:12 PM, Ridvan Gyundogan <[EMAIL PROTECTED]> wrote:
>
> Hi Aravind,
> I think it will not work in this array:
> {1,2,3,4,5,6,7,7,7,7}
> It would give currentelem=7 and c=3 but 7 is not repeated 6 times.
Yes, my method fails on this input.
To avoid this, after running the algo on the array, we can run through the
array once more, checking the number of occurrences of the 'currentelem',
and only output it if the number of its occurrences in the array is n/2 + 1
or more. I think that would solve this problem. Sorry I didn't mention this
previously.
>
> Best
>
>
>
>
>
> > Init c = 1;
> > Init elem = first character in the array.
> > for each element in the array (other than the first one):
> > if currentelem == elem: c++
> > else: c--;
> >
> > if c == 0: elem = currentelem
> >
> > At the end of this loop, the current element specifies the element which
> > appears n/2+1 or more times, IF c is not 0.
> > If c is 0, no element occurs n/2 + 1 times.
> >
> > This takes just O(n) time, as it is just one iteration through the loop,
> and
> > only uses constant space.
> >
> >
> >
> > --
> > Aravind Narayanan | [EMAIL PROTECTED]
> >
>
--
Aravind Narayanan | [EMAIL PROTECTED]
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
