Author |
Topic: majority element (Read 1305 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: majority element
« Reply #1 on: Jun 30th, 2008, 7:02am » |
 Quote  Modify
|
If you read the thread:
on Jul 4th, 2005, 6:17am, towr wrote:| This returns the majority element assuming there is one. You'll still have to check whether there actually is one (by checking whether this element occurs more than N/2 times). |
|
The result the algorithm gives is the element that is the majority element, given that there is one. If you give invalid input (because the premise is that there is a majority element, and your example doesn't have one), then you have to check for that.
|
| « Last Edit: Jun 30th, 2008, 7:05am by towr » |
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
oriole
Newbie
Posts: 32
|
|
Re: majority element
« Reply #2 on: Jun 30th, 2008, 7:06am » |
Quote Modify
|
on Jun 30th, 2008, 7:02am, towr wrote:If you read the thread:
The result the algorithm gives is the element that is the majority element, given that there is one. If you give invalid input (because the premise is that there is a majority element, and your example doesn't have one), then you have to check for that. |
|
In case we have both the conditions that majority may/may not be present, in that case we have to take care of other condition also and the algo proposed wont be applicable.
As the question put on demanded considering both the situation I was under the impression it will take care of both situations.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: majority element
« Reply #3 on: Jun 30th, 2008, 7:19am » |
Quote Modify
|
on Jun 30th, 2008, 7:06am, oriole wrote:| As the question put on demanded considering both the situation I was under the impression it will take care of both situations. |
|
It just requires an additional check, as mentioned in the post.
Besides, the question asks "write an O(N) algorithm to find the majority element if it exists"; I wasn't asked to do anything in particular if it didn't exist 
And it's not like it's the only detail missing from the pseudo code in the orange block, no libraries were included, no output written, nor input read, no function wrapper. It just gives the bare bones of the algorithm. This has two advantages, 1) I can indulge my laziness, 2) it doesn't complicate the understanding of the code by obfuscating the main points in a lot of needless details.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: majority element
« Reply #4 on: Jun 30th, 2008, 7:31am » |
Quote Modify
|
Here, I'll humour you.
Code:
extern find_majority_element_assuming_it_exists(Array arr);
function find_majority_element(Array arr)
{
arr.element_type element = find_majority_element_assuming_it_exists(arr);
unsigned counter=0;
for(unsigned i=0; i < arr.size(); i++)
if(arr[i] == element) counter++;
if (counter > n/2)
return element;
else
throw HONESTLY_NOONE_TOLD_ME_WHAT_TO_DO_IF_THERE_WASNT_A_MAJORITY_ELEMENT_EXCE PTION;
} |
|
Where the function find_majority_element_assuming_it_exists implements the code in the other thread, which finds the majority element if it exists.
|
| « Last Edit: Jun 30th, 2008, 7:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
oriole
Newbie
Posts: 32
|
|
Re: majority element
« Reply #5 on: Jun 30th, 2008, 10:39am » |
Quote Modify
|
on Jun 30th, 2008, 7:31am, towr wrote:Here, I'll humour you.
Code:
extern find_majority_element_assuming_it_exists(Array arr);
function find_majority_element(Array arr)
{
arr.element_type element = find_majority_element_assuming_it_exists(arr);
unsigned counter=0;
for(unsigned i=0; i < arr.size(); i++)
if(arr[i] == element) counter++;
if (counter > n/2)
return element;
else
throw HONESTLY_NOONE_TOLD_ME_WHAT_TO_DO_IF_THERE_WASNT_A_MAJORITY_ELEMENT_EXCE PTION;
} |
|
Where the function find_majority_element_assuming_it_exists implements the code in the other thread, which finds the majority element if it exists. |
|
well instead of putting this whole new check just check the count variable (in the previous thread). It should be > 2
|
| « Last Edit: Jun 30th, 2008, 10:40am by oriole » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: majority element
« Reply #6 on: Jun 30th, 2008, 11:55am » |
Quote Modify
|
on Jun 30th, 2008, 10:39am, oriole wrote:| well instead of putting this whole new check just check the count variable (in the previous thread). It should be > 2 |
|
Not necessarily. It may be no more than 1 (e.g. if you alternate the majority element and other elements; [4,1,4,2,4,3,4] -> count goes 1,0,1,0,1,0,1).
And it may be > 2 for elements that aren't the majority element (e.g. if you trail any sequence with a new element that occurs less than half the time (and more than twice); [1,2,3,4,5,5,5] -> count goes 1,0,1,0,1,2,3).
You need to run through the array again to make sure. Or you need another algorithm entirely. And considering this one is fairly cheap (only two checks for every element), I doubt it would do better over all.
|
| « Last Edit: Jun 30th, 2008, 11:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print