Perfect and elegant solution for finding a number m if it occurs more than n/2.
regards
Arunachalam.
On 2/21/06, daizi sheng <[EMAIL PROTECTED]> wrote:
if there is an element occurring more than n/2 times in Q, we can find
it as following.
if x \in Q and y \in Q and x != y, we can just drop both of them and
do not change the
answer. so the algo. is like:
c = 0
for i = 1 to n {
if(c == 0) {
c = 1
x = Q_i
}else{
if(Q_i != x) c--
else c++
}
}
then we claim x is the answer.
then we can count the occurrence of x in Q to give to final answer!
2006/2/21, kool_guy <[EMAIL PROTECTED]>:
>
> Given a set Q of n numbers, and you want to test if more than n/2
> numbers are equal. You are only allowed to compare two numbers
> directly. Give an algorithm that uses O(n log n) comparisons.
>
>
>
>
--
myblog:
--
===================================
want to know more about me
http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
- [algogeeks] Re: test if more than half of numbers are equal Arunachalam
