@ Narsimha Raju : yes only one such can element exit...
@Pre :
Is there any algorithm to find median or mode in o(n)...
because common approach are :
Find the Median of: 9, 3, 44, 17, 15 (Odd amount of numbers)
Line up your numbers: 3, 9, 15, 17, 44 (smallest to largest)
The Median is: 15 (The number in the middle)
Find the mode of:
9, 3, 3, 44, 17 , 17, 44, 15, 15, 15, 27, 40, 8,
Put the numbers is order for ease:
3, 3, 8, 9, 15, 15, 15, 17, 17, 27, 40, 44, 44,
The Mode is 15 (15 occurs the most at 3 times)....
On Wed, Sep 22, 2010 at 8:01 AM, Narsimha Raju <cnarsimhar...@gmail.com>wrote:
> @coolfrogs: How can more than one element exist of 2n/3 times repeated..
> @dave: can u add that for loop and send as i tried but could not succeed
>
> On Wed, Sep 22, 2010 at 6:23 PM, coolfrog$ <
> dixit.coolfrog.div...@gmail.com> wrote:
>
>> solution in o(n log n)
>> can be ( as if solution exit only one element cam be a majority element
>> in the given array)
>> 1. sort the array in O(nlogn)
>> 2. x = a[2n/3]
>> if(a[0]==x)
>> { if(x== a[(2n/3])+1)
>> return (x)
>>
>> }
>> On Wed, Sep 22, 2010 at 5:53 AM, Dave <dave_and_da...@juno.com> wrote:
>>
>>> Try something like this:
>>>
>>> int FindMajority( int n , int a[] )
>>> {
>>> int majority = a[0];
>>> int count = 1;
>>> for( i = 1 ; i < n ; ++i )
>>> {
>>> if( a[i] == majority )
>>> {
>>> ++count;
>>> }
>>> else
>>> {
>>> if( count == 0 )
>>> {
>>> majority = a[i];
>>> count = 1;
>>> }
>>> else
>>> {
>>> --count;
>>> }
>>> }
>>> }
>>> return majority;
>>> }
>>>
>>> It will find an element that occurs at least n/2 times in the array.
>>> If you need to verify that the element occurs 2n/3 times, add a loop
>>> to count the number of occurences of majority before the return.
>>>
>>> On Sep 21, 10:42 pm, pre <pre.la...@gmail.com> wrote:
>>> > Hi all,
>>> > pls help me solve this problem..
>>> > Design an algorithm to find the majority element of an array..
>>> > majority element must be an element tht has the cardinality greater
>>> > than 2n/3 where n is the number of elements in the array and the time
>>> > complexity must be a linear time.. ie o(n)..
>>> >
>>> > hint : use mode or median to solve ..
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards,
> C. Narsimha Raju
> MS, IIIT Hyderabad.
> http://research.iiit.ac.in/~narsimha_raju/<http://research.iiit.ac.in/%7Enarsimha_raju/>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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?hl=en.
