Algorithms | majority element

Question

Im trying to write an algorithm to return true if a majority element exists in an array and false otherwise. edit: i can only tell if two elements are equal. meaning i can't use < or >, only =. edit: the solution should be in a divide-and-conquer method. its runtime shouldnt go over nlogn, and i wrote something in java but im not sure if it is correct and how to calculate the runtime.. here is what i got:

public static boolean MajorityBoolean(int[] arr) {
    int c;
    int n = arr.length;
    for (int i = 0; i < n; i = i + 2) {
        System.out.println("*");
        if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) {
            c = 0;
            for (int j = 0; j < n; j = j + 1)
                if (arr[j] == arr[i])
                    c = c + 1;
            if (c > n / 2)
                return true;
        }
    }
    return false;
}

I added a homework tag, since it seems to be the case. If I am mistaken, please correct me. — amit, Apr 14 '12 at 14:37
possible duplicate of [Find majority element in array](http://stackoverflow.com/questions/4325200/find-majority-element-in-array) — erickson, Apr 14 '12 at 15:13
Specifically, [this](http://stackoverflow.com/a/9487018/3474) is the best solution to the duplicate question. — erickson, Apr 14 '12 at 15:20

amit · Accepted Answer · 2012-04-14T15:01:11.210

The runtime of the described algorithm is O(n^2). The outer loop is executed n/2 times, thus the inner counter j is resetted n/2 times, and thus the inner loop is executed total of O(n^2) times.

I am not sure I am following the logic behind your idea, but here are two approaches how I'd implement it [in high level pseudo-code]:

(1) create a histogram out of the data:

create a Map<Integer,Integer> [the key is the element and the value is the number of occurances]
iterate the array, and for each element count how many times it appears
iterate the histogram and find if there is a unique maxima.
If there is - return true, else return false.

This approach is average of O(n) if you use a HashMap as the map.

(2) sort and find max occurances:

Sort the array - as the result, all equal elements are adjacent to each other. You can use Arrays.sort(array) for sorting.
Count how many times each element appears [similar to the histogram idea], and find if there is a unique maxima. You don't actually need to maintain the data for all elements, it's enough to maintain for the top 2, and at the end to see if they are identical.

This solution is O(nlogn) average + worst case [actually, depending on the sort - merge sort gives you O(nlogn) worst case, while quick-sort gives you O(n^2) worst case, and both are O(nlogn) on average case].

EDIT:

I misunderstood the problem at hand, I thought you are looking if there is a unique maxima. These 2 solutions still fits for the problem, you just need to modify the last step of each [to check if the most occuring element appears more then half of the times, which is again fairly easy and doable in O(n)].

Also, there is another solution: Use selection algorithm to find the median, and after finding it, check if it is a majority element, and return if it is. Since selection algorithm is divide-and-conquer based solution, I think it fits your needs.

first, thanks for you help! second, my idea was that in every array which has a majority element, there must be two identical numbers one after the other (considering that the array is kind of a circle, such that the last element is close to the first). is that a good\correct idea? btw, apparently i had to write the algorithm in a divide-n-conquer method, so mine isn't good (also its runtime is O(n²) which is more than )(nlogn)). — shachar0n, Apr 14 '12 at 14:54
@shachar0n: (1) I still don't follow the logic, why is the array circular? :\. (2) I misunderstood the question, I thought you were looking if there is a unique maxima. These two solutions still fits the problem at hand, with sloght modification in the last step of each solution. (3) The question you are describing can be solved using [selection algorithm](http://en.wikipedia.org/wiki/Selection_algorithm). Find the median - and then look if it the majority element. Selection algorithm is actually a devide and conquer solution. — amit, Apr 14 '12 at 14:58
(1) what i ment was that if an array has a majority element, that it must have two close elements which are the same. if the array is like this: 1010101 , then the last and first elements are the same - and that's what I mean by treating the array like a circle (using modulu %). (2)(3) i forgot to mention another restriction: I can only know if two elements are the same but i can't tell if one is larger or smaller than the other, meaning i can only use = and can't use: > <. — shachar0n, Apr 14 '12 at 16:55

coder101 · Answer 2 · 2015-02-17T22:21:32.170

A majority element in an array A[] of size n is an element that appears more than n/2 times

public static boolean find(int[] arr, int size) { 
int count = 0, i, mElement;
for (i = 0; i < size; i++) {
    if (count == 0)
        mElement = arr[i];
    if (arr[i] == mElement) 
        count++;
    else
        count--;
}
count = 0;
for (i = 0; i < size; i++)
    if (arr[i] == mElement)
        count++;
if (count > size/2)
    return true;
return false;
}

score 0 · Answer 3 · edited May 23 '17 at 11:45

0

Following is an O(n) solution Find Majority Element

edited May 23 '17 at 11:45

Community

1
1

answered Apr 14 '12 at 14:48

MoveFast

3,011
2
27
53

This is points to a good solution, but you should vote to close duplicate questions if you can, or simply make a comment on the question if you can't. – erickson Apr 14 '12 at 15:25

Algorithms | majority element

3 Answers3