Home Arrays Find the majority element in an array. (Method 2)

Find the majority element in an array. (Method 2)

by nikoo28
0 comment

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted.

Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8.
Output: Majority Element = 8

We discussed the most naive method to achieve this in our previous post. To improve the time complexity of our problem we can apply sorting technique. If we sort the array, all the like elements will be placed together. When all similar elements are placed together we do not need 2 loops to maintain the count of elements. What we do is:-

  • Step 1: Sort the given array
  • Step 2: Start from the first element and set the count as 1.
  • Step 3: Keep incrementing the count until we see the same element.
  • Step 4: Once we see a different element, reset the count to 1 and repeat with step 3.

majority_element
So the sample code for the above algorithm can be written as:-

void printMajorityElement(int arr[], int size)
{
	quickSort(arr,size);

	int count = 0;
	int i,j=0;
	int majority = 0;
	int found = 0;

	for(i = 0;i<size;i++)
	{
		count = 1;
		j = i+1;
		if(j == size)
			break;
		while(arr[j] == arr[i])
		{
			count++;
			j++;
		}

		i = j - 1;
		if(count > (size/2))
		{
			found = 1;
			majority = arr[i];
			break;
		}
	}

	if(found)
		printf("Majority element = %d",majority);
	else
		printf("Majority element not present");
}

Time Complexity:- O(nlog(n))
Space Complexity:- O(1)

Method 1 – Using sorting.

Method 3 – Using a single scan, better time complexity, faster.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More