Write a java program to find and print the most repeated element in the array in O(n). If there is more than one number having the same highest frequency, then print the smaller value.
Example:
1 2 3 4 5 | Input - [1, 7, 2, 6, 6, 8, 1, 3, 2, 6] Output - 6 Input - [1, 3, 2, 5, 9, 2, 1, 3, 1, 2] Output - 1 |
To find the number which has the highest frequency, we have to follow the following steps.
- Sort the array in Ascending Order.
- Loop through the array and count the frequency of each element.
- Check for each number if thier frequency is greater than the old max frequency.
- If yes then update the max frequency and note the number.
- Repeat the steps for all distinct elements.
- Output the the number which has highest frequency or repeated most times in the array.
Initially, the max frequency will be Integer.MIN_VALUE, which stores the minimum available integer supported by the machine.
We have sorted the array because the same elements will come together; hence, it will be easier to count the frequency of each element in O(n).
So, overall we are trying to do the following as depicted in the image.
Let’s do the same in Java.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.Arrays; public class Main { public static void main(String[] args) { int arr[] = {2, 4, 6, 4, 2, 4, 5, 8}; //Sorting array in Ascending Order Arrays.sort(arr); int element = Integer.MIN_VALUE, max_count=1, count=1; for(int i=1; i<arr.length; i++){ //count the same element if(arr[i] == arr[i-1]) count++; else{ //Compare the counted frequency with max_count if(count>max_count){ //Update if found greater frequency max_count = count; element = arr[i-1]; } //Reset Count count =1; } } System.out.println(element+": "+max_count); } } |
Output- 4:3
Time Complexity – O(n)
Space Complexity – O(1)
There are other several ways to find the most repeated element or the element with the highest frequency. I have only mentioned which is efficient and best for programming.
If you have any doubts or suggestions, then comment below.
Mohd Amer Khan
9 Dec 2019Brilliant explaination thanks a lot