Simple Java program to find the first repeating element in array
- Let say there is an array
- int array[]={8,7, 5, 3, 4, 3, 5, 6};
- Now if you see the first repeating element is 5
- To solve this, First think comes to our mind is use iteration.
- then use Set and one counter variable.
- Since we need the first repeating element , do the iteration from array.length instead of 0. So that the first repeating element will come at the end in the iteration
public class FirstRepeatingElement {
public static void main(String[] args) throws java.lang.Exception {
int array[] = { 8, 7, 5, 3, 4, 3, 5, 6 };
int min = -1;
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Traverse the input array from right to left
for (int i = array.length - 1; i >= 0; i--) {
// If element is already in hash set, update min
if (set.contains(array[i])) {
min = i;
}
else {
// Else add element to hash set
set.add(array[i]);
}
}
if (min != -1) {
System.out.println("The first repeating element is " + array[min]);
} else {
System.out.println("There are no repeating elements");
}
}
}
- As you can see, Hashset will not allow duplicate, whenever it finds the duplicate element just increment the counter min variable.
- And also it iterate the for loop in reverse direction.
Alternate approach is Use LinkedHashMap.
- Initialize LinkedHashMap<Integer, Integer> hMap=new LinkedHashMap<>();
- Iterate the array element in for loop
- Check the map contains the same element already
- if not put the element in hMap with value 1
- if already found, then just increment the value to +1
for(int i=0;i<arr.length;i++) {
if(hMap.get(arr[i]) == null) {
hMap.put(arr[i], 1);
}else {
int val=hMap.get(arr[i]);
hMap.put(arr[i],val+1);
}
}
Finally, iterate the Map, the print the first repeating element in array.
No comments:
Post a Comment