Yes this seems to be working.
On Feb 3, 6:50 pm, "Aravind Narayanan" <[EMAIL PROTECTED]> wrote:
> 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 [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
-~----------~----~----~----~------~----~------~--~---
