Let's start by understanding the problem statement of this task.
You are given an array of integers, your work is to find the element which occurs more than n / 2 times in the array, where “n” is the total length of the array.
Hint:
For finding the element in the array which occurs more than n / 2 times can be done in by using a hashmap where the programmers can store the element and its occurrence in the map.
Quick Think:
For creating the hashmap we need to keep the following things in mind:-
- The elements should be entered in the hashmap with its frequency as 1 for the first time and subsequently if it occurs more than once then keep incrementing its frequency and keep check if it is greater than the value n / 2 then output the element.
- While checking for the value of the occurrence of the elements we need to increment the frequency of the element first and then pass the frequency to the map, otherwise, we may lose one count of the element.
Algorithm:
Create a function with the argument as the array of integers, and it’s size, and then follows the steps below to get the desired output:-
Step1: After creating the function we need to define the hashmap in java which is given in the code below of integer type with a field of keys to store the count of each element.
Step2: Now, we will traverse through the array once and check if the element in the hashmap exists from before, if yes then we will get the frequency of the element and increment it by one (as said in the Quick Think section) and then go to step 3 else go to step 5.
Step3: Then check for the frequency obtained in step 2 if the frequency of the element is greater than the value of n / 2 then output the element and then terminate the process, else go to step 4.
Step4: Insert the element into the hashmap along with it’s updated frequency in step 2.
Step5: Insert the element into the hashmap with its frequency as 1.
Step6: If no element in the array has a frequency greater than the value of n / 2 then the there is no element and hence, output no element found.
Implementation Of The Above Algorithm:
Now let's see the implementation of the above algorithm,
import java.util.*;
class element
{
/*Function to find the majority element in the array. */
public static void element(int arr[], int n)
{
HashMap<Integer, Integer> set = new HashMap < > ();
for (int i = 0; i < n; i++)
{
if (set.containsKey(arr[i]))
{
int count = set.get(arr[i]) + 1;
if (count > n / 2)
{
System.out.println("The element is = " + arr[i]);
return;
}
else
set.put(arr[i], count);
}
else
set.put(arr[i], 1);
}
System.out.println("No majority element found");
}
/*Driver program to test the above function. */
public static void main(String[] args)
{
int arr[] = new int[]
{ 3, 3, 4, 2, 4, 4, 2, 4, 4 };
int n = arr.length;
element(arr, n);
}
}
The time complexity of the above algorithm is- O(n).
The output of the above algorithm is:- The majority element is:- 4.
Explanation Of The Above Algorithm:
Let us consider an example array as given in the above algorithm as shown in the above diagram, follow the steps below to reach the output:-
- Since there are no elements in the hashmap, so we will insert the elements one by one in our hashmap.
- First, the element 3 is inserted in the map with frequency as one, now again we encounter other 3 and this time the frequency of the element is two and which is not greater than the value of n / 2 i.e., four, so we will push the element 3 in the hashmap back with the updated frequency as two as shown in the above diagram.
- Now, we encounter the number 4 which is inserted in the map with frequency as one this time the frequency of the element is two and which is not greater than the value of n / 2 i.e., four, as shown in the above diagram, so we move to the next step.
- Similarly, we encounter the number 2 which is inserted in the map with frequency as one this time the frequency of the element is two and which is not greater than the value of n / 2 i.e., four, as shown in the above diagram, so we move to the next step.
- We again encounter the number 4 which is inserted in the map with it’s updated frequency as two which is not greater than the value of n / 2 i.e., four, as shown in the above diagram, so we move to the next step.
- Again, we encounter the number 4 which is inserted in the map with it’s updated frequency as three which is not greater than the value of n / 2 i.e., four, as shown in the above diagram, so we move to the next step.
- We encounter the number 2 which is inserted in the map with frequency as two which is not greater than the value of n / 2 i.e., four, as shown in the above diagram, so we move to the next step.
- Again, we again encounter the number 4 which is inserted in the map with it’s updated frequency of four which is not greater than the value of n / 2 i.e., four, as shown in the above diagram, so we move to the next step.
- Finally, we again encounter the number 4 which is inserted in the map with it’s updated frequency as five which is certainly greater than the value of n / 2 i.e., four, as shown in the above diagram, so we output our result as 4.
