How to find a majority element in an Unsorted List in Python
In this tutorial, we will see how to find a majority element from an unsorted list using Python. Here, the definition of the majority element will be defined below in the problem statement.
Problem Statement for finding Majority element from an unsorted list in Python
A list is given as an input that is not sorted. We have to find the majority element. Here majority element is the element that appears more than half the value of list size.
i.e, an element whose frequency is more than (len(list)/2) times.
Here I am assuming the list is non-empty and the majority element will always exist in the list.
Input – [2 , 3 , 2 , 2 , 4]
Output – 2
Explanation:- because its frequency is more than (5/2 = 2.5) as len(list) = 5.
We will use simple operations to solve this problem. This problem can be solve using extra space and also without using extra space. But, the more efficient solution will be the one without using extra spaces. So I will discuss that approach and solution i.e without using extra spaces.
You guys can try this question using extra spaces that will also help in developing the logic in different ways.
Code for the given problem :
def maj(LIST): if(len(LIST) == 1): # if length of LIST is 1 then half of length is 0 (int) so LIST is OUTPUT since its frequency is 1>0 return(LIST) LIST.sort() # sorting the LIST in ascending order count=1; n = len(LIST)/2 # finding half of length of LIST for i in range(0,len(LIST)-1): if(i == len(LIST)-2): # this condition will check for every LIST[-1] and LIST[-2] elements for every LIST if(LIST[i] == LIST[i+1]): count = count+1 # incrementing the value if same value if(count>n): return(LIST[i]) elif(LIST[i] == LIST[i+1]): count = count+1 # incrementing the frequency if same value elif(LIST[i] != LIST[i+1]): if(count>n): # checking frequency of a element is greater than n or not return(LIST[i]) else: count=1 # if not greater than n then again assign count = 1 and if loop not completed again start the same work via loop print(maj([2,1,2,2,4])) print(maj()) print(maj([1,2])) print(maj([1,1]))
2 1 None 1
Hope this tutorial helps you to understand the concept of this problem statement.
As I mentioned before trying to solve this problem using extra space also.Comment below if you like this content and also you can give me any suggestions regarding this tutorial.
Also read: Python List and Basic Python Set method