Divide and Conquer - PeiShang/Algorithms-Notes GitHub Wiki

Given a list of n non-negative integers a₀, a₁, ..., a_n-1, return the majority element (element that appears more than n/2 times) or -1 if there doesn't exist such element.

• If the majority element of the list A exist, it must also be the majority element for one of A's halves. That means if we find the majority elements of each halve of A, then the 'final' must comes from the two candidates, if exist.
• Like the progress of merge in merge sort, we have to make a 'check' process to check witch candidate element is the final majority element (or none of them is).
• The base situation is that if the list consist with only one element [a₀], then a₀ is the majority element.

get_majority_element(a, l, r):
    # a is the list, l is the left index, r is the right index
    if only one element in a:
        return a[0]
    # cut the list into two halves
    mid = l + r / 2
    # get majority element of each halve
    m1 = get_majority_element(a, l, mid)
    m2 = get_majority_element(a, mid, r)
    # check if the candidates are true majority element, this can be done by count m1 and m2 in a[l:r] and check if > len/2
    major_element = check_candidates(a, l, r, m1, m2)
    return major_element