On Dec 11, 11:03 am, "Miroslav Balaz" <gpsla...@googlemail.com> wrote: > i think it will not perform good, if you have cards like this 1 2 3 4 5 5 5 > 5
Actually it's not all that bad in this case, it terminates when it reaches the first occurence of 5. (1 2 3 4 5 5 5 5 5) is much worse. > the supposed solution is, keep one counter and one candidate > first , the candidate is the first element, and counter is 1 > if the next card equals candidate increase the count to 1, else decrease it > if counter is zero you must take the new value as candidate, i am not sure > if you do this before decreasing. > I am only telling you what i remember from lecture. > And at the and cehck if the candidate is correct. > And it can be proven that if there is more than n/2 same cards the candidate > will be one of them Clever! I'll have to remember that one. Worst case is only two passes. A bit of a shame it only works when the target set is larger than half. -- Geoff --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
