Why not do this as a type of counting sort? It's obvious that these are only going to be integers, so if you know the range, a counting algorithm would be best.
Initialize your counting array to 0. Loop through your original array for each element a, add 1 to the index a of the counting array. Loop through the counting array looking for a an element with value >= N/2. The index where you find that element is the majority. It can't be any other number because there's less than (or equal to) N/2 elements left, and so any other number will be less than or equal to the number you've found. I'm pretty sure that this is an O(n) algorithm, though I guess for large numbers it's probably slower than the stack algorithm mentined above. --Guillaume C.L.-- --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
