0
$\begingroup$

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array)

I came up with this linear divide and conquer algorithm, but I'm not sure if it's correct. It returns an array with two elements, the name of the majority element and a number that is less than or equals to its occurrences. Can someone help to prove/disprove it?

def findMajority(arr):
    if len(arr) == 1:
        return [arr[0], 1]
    else:
        leftHalf = findMajority(arr[:len(arr)/2])
        rightHalf = findMajority(arr[len(arr)/2:])

        if leftHalf[0] is None and rightHalf[0] is not None: #Left half is indeterminate
            return [rightHalf[0], rightHalf[1]]

        if leftHalf[0] is not None and rightHalf[0] is None: #Right half is indeterminate
            return [leftHalf[0], leftHalf[1]]

        if leftHalf[0] is None and rightHalf[0] is None: #Both halves are indeterminate
            return [None, 0]

        if leftHalf[0] == rightHalf[0]: #Majority in both halves is the same
            return [leftHalf[0], leftHalf[1] + rightHalf[1]]

        elif leftHalf[1] < rightHalf[1]: #Right majority has more occurrences
            return [rightHalf[0], rightHalf[1]]

        elif leftHalf[1] > rightHalf[1]: #Left majority has more occurrences
            return [leftHalf[0], leftHalf[1]]

        else: #There is no winner between the two halves and they have equal occurrences
            return [None, 0]

EDIT: It returns the wrong answer for [2,2,2,2,1,1,1,0,1,1,1,0,1,1,1,0] . So it doesn't work.

$\endgroup$
  • $\begingroup$ @xavierm02 But in this case there is no majority, there needs to be more than $n/2$ occurrences $\endgroup$ – Jack Black Mar 3 '17 at 17:40
  • $\begingroup$ @xavierm02 There is still no majority, there needs to be an element with 5 or more occurrences $\endgroup$ – Jack Black Mar 3 '17 at 17:44
  • $\begingroup$ How about $[0;1;1;1]$? $\endgroup$ – xavierm02 Mar 3 '17 at 17:46
  • $\begingroup$ @xavierm02 It works in this case. $\endgroup$ – Jack Black Mar 3 '17 at 17:48
  • 1
    $\begingroup$ If you're looking for a linear time algorithm, try this en.wikipedia.org/wiki/… $\endgroup$ – skankhunt42 Mar 3 '17 at 17:59
2
$\begingroup$

It's not correct. On input [a a b c], the left side yields [a, 2], the right side yields [nil, 1]. They would be merged into [a, 2].

I'll outline a linear time solution. If there exists a value $x$ such that more than $n/2$ of the elements of $A$ have value $x$, then certainly the $n/2$-th order statistic of $A$ must be $x$. The selection problem is solved in linear time using, for example, median of medians; checking that such value does indeed appear at least $n/2$ times is trivially linear time.

$\endgroup$
  • $\begingroup$ But the only requirement is that it output the majority element if it exists. In this case 0 will need to appear more than 2 times so I don't think it is relevant for this case? $\endgroup$ – Jack Black Mar 3 '17 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.