CODEWITHSUNDEEP
pythonalgorithmsorting
Daniel Chepenko
Daniel Chepenko

Reputation: 2268

Majority Element using divide-and-conquer algorithm

everyone! An element of a sequence of length n is called a majority element if it appears in the sequence strictly more than n/2 times.

The goal in this code problem is to check whether an input sequence contains a majority element.

I'm trying to solve this problem, using merge sorting algorithm

My strategy:

  1. Sort sequence, using merge algorithm

  2. Find an occurrence of each element in sorted list. If it is more than n/2, return 1. As the list is sorted I want to go through the list, and if next element is differs from previous one counter stops and compare it with n/2

    def merge(left,rigt):
    result = []
    i = j = 0
    while i < len(left) and j < len(rigt):
        if left[i] <= rigt[j]:
            result.append(left[i])
            i += 1

        else:
            result.append(rigt[j])
            j += 1

    result += left[i:]
    result += rigt[j:]

    return result

def merge_sort(a):
if len(a) <= 1:
    return a

middle = len(a)//2

left = a[:middle]
right = a[middle:]

left = merge_sort(left)
right = merge_sort(right)

return list(merge(left,right))

def get_major_element(a,n):

k = 1

for i in range(0,len(a)-1):
    if a[i] == a[i+1]:
        k += 1

if k > n/2:
    return 1

else:
    return 0

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n = data[0]
    a = data[1:]
    m = merge_sort(a)
    print (get_major_element(m,n))

The result I get is invalid. I guess, that I can do that without initial sorting, but I can't get which step should I rewrite! Can anyone help please?

Upvotes: 3

Views: 4204

Answers (7)

Jason Chu
Jason Chu

Reputation: 1

https://stackoverflow.com/a/56161162/13467399

Thanks for your post, mate. I was scratching my head over the problem. I see that you were wondering why the author finds the mid point by (left + right - 1) // (2 + 1).

It's because the "right" here is taking the size the array and arrays always start at 0 not 1, that answers for adding 1 in the divisor.

Actually, the mid point can be calculated using (left + right) / 2.

Sorry that I can't comment in your post since I don't have the privileges.

Upvotes: -1

R Chang
R Chang

Reputation: 63

# Uses python3
import sys

def get_majority_element(a, left, right):
    if left == right:
        return -1
    if left + 1 == right:
        return a[left]


    left_elemt = get_majority_element(a,left,(left + right - 1) // 2 + 1)
    right_elemt = get_majority_element(a,(left + right - 1) // 2 + 1,right)

    l_count = 0
    for i in range(left,right):
        if a[i] == left_elemt:
            l_count += 1
    if l_count > (right - left)//2:
        return left_elemt

    rcount = 0
    for i in range(left, right):
        if a[i] == right_elemt:
            rcount += 1
    if rcount > (right - left) // 2:
        return right_elemt

    return -1


if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    if get_majority_element(a, 0, n) != -1:
        print(1)
    else:
        print(0)

I spent a lot of time on this one. had the same question and confusion as you. It appears that the function for middle should be (left + right - 1) // 2 + 1 (credit to mablatnik's git ) (altho I have not figure out why yet)

Upvotes: 0

Deep Shikha
Deep Shikha

Reputation: 19

It worked for me in java

k=1;
for(c=0;c<n-1;c++){
    if(array[c]==array[c+1])
      k+=1;

    else k=0;


    if (k > n/2){
      System.out.print("1");
      break;

    }
  }
  if (k <=n/2){
      System.out.print("0");
}

Upvotes: -1

ffao
ffao

Reputation: 876

Divide your array into two halves, the left half and the right half. Note that if an element is the majority of the whole array, then it's the majority of at least one of the halves.

So to find the majority of an array, recursively find the majority of both halves, and then with a single pass on the array count how many times both of the candidates appear in the whole array, to check which of them is the majority of the whole array.

Upvotes: 3

Abhinav
Abhinav

Reputation: 301

check moore's algorithm, it works in two pass and finds majority element in O(N)

Or simply sort array and element on middle index (startIndex + endIndex)/2 should be majority element. (if there is majority element at all in array).

Upvotes: 0

nephlm
nephlm

Reputation: 553

If there is a reason that you aren't using built in sort and counting mechanisms pointed out by others, this will do it in a single pass without using anything but very basic datatypes. Many of the built in operations may contain loops that could make them O(n**2) in the worst case.

def getMajor(L):
    best = None
    elements = {}
    for element in L:
        elements[element] += 1
        if elements[element] > elements.get(best, 0):
            best = element

    if elements.get(best, 0) > len(L)/2:
        return best, elements.get(best, 0)
    else:
        return None, 0

Upvotes: 0

Byte Commander
Byte Commander

Reputation: 6746

I would create a set of unique elements and count their occurrences in the original list, then compare the biggest value with the list length:

def get_major_element(my_list):
    available_items = set(my_list)
    max_count, max_item = max((my_list.count(item), item) for item in available_items)
    return max_item if max_count > len(my_list)/2 else None

See this code running on ideone.com

Upvotes: 1

Related Questions