What is a majority element ?
If you are refering to your previous post , then , use hashing
On Feb 13, 10:12 pm, Akshata Sharma akshatasharm...@gmail.com wrote:
oops... ignore the post :-/
On Feb 13, 10:07 pm, Akshata Sharma akshatasharm...@gmail.com wrote:
Given an element and an array,
oops... ignore the post :-/
On Feb 13, 10:07 pm, Akshata Sharma akshatasharm...@gmail.com wrote:
Given an element and an array, how will you find whether the element
is the majority element of the array or not in linear time?
--
You received this message because you are subscribed to the
One problem in your algorithm is that the additional array has to be
large enough to handle all of the values in the array, so, e.g.,
multiply all of your values by a million and you will see that the
work goes up by a factor of a million.
It can be done without the additional array, and
Hi Bittu,
Your algorithm uses Linear extra space. which is proportional to the
input used.
There is a better algorithm which is linear in time and does alot
better .
int Majoritycount(int [] A) {
int ctr=1;
//counter is a variable to indicate the relative importance of the
element. as
**Presume the majority exists**, the following algo use O(1) space and
only scan the array one pass.
It is simple idea of counting. If there exists a majority elements in
the array, it must be the remaining element on the counter after we
consider all elements.
int getMajority(int A[], int n){
ericunfuk wrote:
Arunachalam wrote:
Search the groups, this problem is already solved in O(n) time in the
groups.
regards
Arunachalam.
I solved it with n/2 case, I dont see how to do that with n/t, t
arbitrary.
I think this is equivalent to sorting. Consider the special case
hash table :)if u dont like O(n) space, a st.forward approach is sorting. this will take of any value of m, but ofcourse O(nlgn) time On 11/1/06, ericunfuk
[EMAIL PROTECTED] wrote:
Dear all,I have worked out the following algorithm for finding the majorityelement(the element occurs more than n/2
It seems that you gotta use the median algrithm. Here's some idea
without implementation, I wish it will help.
if the array has an odd number of lements, then the array can be
devided into 3 parts:
Head, Median, Tail
If an element occurs more than n/m times, then at least in Head or in
Tail it
Search the groups, this problem is already solved in O(n) time in the groups.
regards
Arunachalam.
On 11/2/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
It seems that you gotta use the median algrithm. Here's some ideawithout implementation, I wish it will help.
if the array has an odd number of
Arunachalam wrote:
Search the groups, this problem is already solved in O(n) time in the
groups.
regards
Arunachalam.
I solved it with n/2 case, I dont see how to do that with n/t, t
arbitrary.
Thanks
--~--~-~--~~~---~--~~
You received this message
I think the straightforward method it as followed:
Suppose n = 2, m = 7
Check the 2-th ,4-th,6-th elements
For general n m, there will be at most m/n such elements, by check them
one by one, u just need
O(m/n * m) time
If n = theta(m), of course, the algorithm is O(m).
Otherwise, if n m,
I think there should be an algorithm that uses the theta(n) finding
median subroutine. Somehow we divide and conquer, i.e. some
generalization of n/2 majority element case.
Thanks
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the
12 matches
Mail list logo
