Divide And Conquer. Find The Majority Of Element In Array

I am working on a python algorithm to find the most frequent element in the list. def GetFrequency(a, element): return sum([1 for x in a if x == element]) def GetMajorityEleme

Solution 1:

I wrote an iterative version instead of the recursive one you're using in case you wanted something similar.

def GetFrequency(array):
    majority = int(len(array)/2)
    result_dict = {}
    whilearray:
        array_item = array.pop()
        if result_dict.get(array_item):
            result_dict[array_item] += 1else:
            result_dict[array_item] = 1if result_dict[array_item] > majority:
            return array_item   
    return max(result_dict, key=result_dict.get)

This will iterate through the array and return the value as soon as one hits more than 50% of the total (being a majority). Otherwise it goes through the entire array and returns the value with the greatest frequency.

Solution 2:

defmajority_element(a):
    returnmax([(a.count(elem), elem) for elem inset(a)])[1]

EDIT

If there is a tie, the biggest value is returned. E.g: a = [1,1,2,2] returns 2. Might not be what you want but that could be changed.

EDIT 2

The pseudocode you gave divided into arrays 1 to k included, k + 1 to n. Your code does 1 to k - 1, k to end, not sure if it changes much though ? If you want to respect the algorithm you gave, you should do:

elemlsub = GetMajorityElement(a[:k+1])  # this slice is indices 0 to kelemrsub = GetMajorityElement(a[k+1:])  # this one is k + 1 to n.

Also still according to your provided pseudocode, lcount and rcount should be compared to k + 1, not k:

if lcount > k + 1:
  return elemlsub
elif rcount > k + 1:
  return elemrsub
else:
  return None

EDIT 3

Some people in the comments highligted that provided pseudocode solves not for the most frequent, but for the item which is present more that 50% of occurences. So indeed your output for your example is correct. There is a good chance that your code already works as is.

EDIT 4

If you want to return None when there is a tie, I suggest this:

defmajority_element(a):
    n = len(a)
    if n == 1:
        return a[0]

    if n == 0:
        returnNone

    sorted_counts = sorted([(a.count(elem), elem) for elem inset(a)], key=lambda x: x[0])

    iflen(sorted_counts) > 1and sorted_counts[-1][0] == sorted_counts[-2][0]:
        returnNonereturn sorted_counts[-1][1]