I used this Java Program to Print Duplicate Elements in an Array as reference.
int[] arr = new int[] {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < arr.length; i ) {
for(int j = i 1; j < arr.length; j ) {
if(arr[i] == arr[j]) {
System.out.print(arr[j] " ");
}
}
}
Output:
2 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5
I think you can already see the problem here. It only works well when there are only two elements that have the same value. But even then, it won't display both the two said values. I've tried to only display arr[i], arr[j], and both arr[i] and arr[j]. But nothing. I am fairly new. I can't get anywhere.
What I want is to display all elements in the array that have at least one identical value.
The result should be:
2 2 3 3 3 4 4 4 4 5 5 5 5 5
Teach me.
I have also tried this GeeksForGeeks: Array elements that appear more than once. Changed the integer array into the same that I have above. It only displayed:
2 3 4 5
CodePudding user response：
It's a fairly simple program so I'm not going to share code, but I will try and explain as best as I can what you can do for it to work.
Note that I am not aiming for optimal solution here, just workable.
What is currently happening:
You have two loops, and outer loop (i) and an inner loop (j), the outer loop goes through the array normally so you can see every number in it, the inner loop goes through the array starting in front of where the outer loop is currently, and printing every number that is a duplicate of the number the outer loop is currently on. This means if a number appears multiple times in the inner loop, it will be printed multiple times. And because it only starts from after the outer loop, if a number appears before that, it won't be detected as a duplicate.
For example 5. When you reach 5 with the outer loop, the inner loop will go through the other four times 5 appears and print it. Then the outer loop goes forward one and the inner loop goes and prints the 3 appearances of 5, etc. You get ten 5s at the end, 4 3 2 1=10 (it decreases in number because the inner loop never goes to numbers before where the outer loop is)
What you can do:
- On the outer loop and before the inner loop starts, add a boolean that keeps track of weather or not this number is a duplicate, it should be false by default
- Then have the inner loop start from the beginning of the array and continue throught the entire array until it finds a duplicate. Make sure to skip the position the outer loop is currently on, you can do so by checking that i and j are the same and using the keyword
continue. If you do find a duplicate, switch the boolean totrueand break the inner loop with the keywordbreak - Now back in the outer loop, just check the boolean and if it is true, print the current outer loop number
CodePudding user response：
What your nested for loops do, is that for each element of the array, it (the inner loop) searches everything after that element for the same number as arr[i]. See how the inner loop starts from i 1?
But for your program to be correct, you need to search the whole array for the same number as arr[i], in order to determine whether arr[i] is duplicated somewhere in the array.
This means starting the inner loop at 0, and breaking the loop as soon as you find one, using a boolean variable to keep track of whether you found one. If you did find one, print arr[i].
int[] arr = new int[] {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < arr.length; i ) {
boolean found = false;
for(int j = 0; j < arr.length; j ) {
if (arr[i] == arr[j] && i != j) {
found = true;
break;
}
}
if (found) {
System.out.print(arr[i] " ");
}
}
Notice that this is a lot of waste. For the first 5, we searched through the array to find another 5, and for the second 5, we are doing the same thing again! We can improve this by using a HashSet. Determining whether something is in a HashSet is asymptotically faster than looping through an array.
Set<Integer> appearedOnce = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
for (int i : arr) {
if (!appearedOnce.add(i)) { // add would return false if i is already in the set
duplicates.add(i);
}
}
for (int i : arr) {
if (duplicates.contains(i)) {
System.out.print(i " ");
}
}
The first part is similar to Alexander Ivanchenko's answer, finding out what the duplicates are. Then, you loop through the array only one more time, conditionally printing out those elements that are in the duplicates set.
CodePudding user response：
Alogrithm
- I sorted the list using Arrays.sort()
Then check if the first element is equal second element (As they sorted so element that has at least identical values should appear) and if the first element is equal to the previous element (As the last element of identical and included it in the result)
int[] arr = new int[] {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,7,8,9,10}; // Sort Array Arrays.sort(arr); for (int i = 1; i < arr.length-1 ; i ) { if(arr[i] == arr[i 1] | arr[i-1] == arr[i]){ System.out.print(arr[i] " "); } }
Output
2 2 3 3 3 4 4 4 4 5 5 5 5 5
CodePudding user response：
- One issue with your code is that your inner-loop starts at: j = i 1;
- When i = 2 and j = 3 then the second two in the array will not find another duplicate.
- Second issue is that you do not break from your inner-loop when you find a duplicate and continue to compare arr[i] to arr[j] and print out to console.
int[] arr = new int[] {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < arr.length; i ) {
for(int j = 0; j < arr.length; j ) {
if(arr[i] == arr[j] && i != j) {
System.out.print(arr[i] " ");
break;
}
}
}
If the array is guaranteed to be sorted then you don't need an additional data structure to check for duplicates.
- Check to the right of the current index for a duplicate. If duplicate doesn't exist in front, then check behind. Be mindful of your array bounds too.
for(int i = 0; i < arr.length ; i ) {
if((i 1) < arr.length && arr[i] == arr[i 1]) {
System.out.print(arr[i] " ");
} else if((i-1) >= 0 && arr[i] == arr[i-1]) {
System.out.print(arr[i] " ");
}
}
CodePudding user response：
You've got more than enough answers. This one fits into one long line using stream / grouping by to find the duplicates, joins those values and then printing:
System.out.println(Arrays.stream(arr).boxed()
.collect(Collectors.groupingBy(Object::toString,LinkedHashMap::new,Collectors.counting()))
.entrySet().stream().filter(entry -> entry.getValue() > 1)
.map(entry -> (" " entry.getKey()).repeat(entry.getValue().intValue()))
.collect(Collectors.joining("")).trim());
Note that the above won't work if the integer values repeat later - example {1,2,1}
CodePudding user response：
You can use Map<Integer, Integer> to count how many times a number exists in the array. Keys are actual numbers from array, values are how many times that number exists in the array. Use LinkedHashMap to keep them in encounter order if that matters. Then just skip any number, which is met only once.
public class Temp {
public static void main(String[] args) {
int[] arr = new int[] {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10};
Map<Integer, Integer> map = new LinkedHashMap<>();
for (int num : arr) {
map.computeIfPresent(num, (key, oldValue) -> oldValue 1);
map.putIfAbsent(num, 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
continue;
}
for (int i = 0; i < entry.getValue(); i ) {
System.out.print(entry.getKey() " ");
}
}
}
}
Edit: Adding stream based version of the above solution:
public class Temp {
public static void main(String[] args) {
int[] arr = new int[] {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10};
Map<Integer, Integer> map = Arrays.stream(arr)
.boxed()
.collect(Collectors.toMap(num -> num, num -> 1, Integer::sum, LinkedHashMap::new));
String result = map.entrySet()
.stream()
.filter(entry -> entry.getValue() > 1)
.flatMap(entry -> {
ValueGenerator generator = new ValueGenerator(entry.getValue());
return Stream.iterate(entry.getKey(), generator, generator);
})
.map(Objects::toString)
.collect(Collectors.joining(" "));
System.out.println(result);
}
private static final class ValueGenerator implements Predicate<Integer>, UnaryOperator<Integer> {
private int count = 0;
private final int maxCount;
public ValueGenerator(int maxCount) {
this.maxCount = maxCount;
}
@Override
public boolean test(Integer num) {
return count < maxCount;
}
@Override
public Integer apply(Integer num) {
count ;
return num;
}
}
}
CodePudding user response：
First of all the code from javatpoint.com you've listed is bad because it's based on assumption that the given array is sorted (only in such case duplicated elements are guaranteed to be consecutive). And it doesn't even mention in the article, that the reason such resources should be avoided.
To find all duplicated elements in the given array, you can use a HashSet, which is an implementation of Set interface which contract ensures that implementing collection should contain only unique elements. HashSet make use of the equals/hashCode implementation of the stored objects to guarantee uniqueness.
Just iterate through the array and offer the element to the set using its method add() which returns a boolean value indicating whether the set was modified or not. If the element gets rejected, that means it has been already encountered.
To see the unique duplicated values, you can declare you might declare a separate set.
int[] arr = {5, 5, 5, 6, 7, 3, 4, 4, 4, 4, 5, 1, 2, 2, 3, 3, 5, 8, 9, 10};
Set<Integer> seen = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
for (int next: arr) {
if (!seen.add(next)) {
System.out.print(next " ");
if (duplicates.add(next)) System.out.print(next " ");
}
}
System.out.println("\nunique duplicated values: " duplicates);
Output:
5 5 5 4 4 4 4 5 2 2 3 3 3 5
unique duplicated values: [2, 3, 4, 5]
This approach is hi-performant and has linear time complexity O(n).
And it's much better than brute-force iteration using two nested for-loops with quadratic time complexity O(n^2). While solving various coding challenges and algorithmic problems, you should avoid brute-force solutions because they always have the worst possible performance.
There's one more useful and performant technic for finding duplicates that worth to be aware of.
Oftentimes, you might find that values have some constraints. For instance, integer elements can be limited to a range [-1000,1000] (whilst the possible range of int is much broader: from -231 to 231 - 1).
In such cases, you can create an auxiliary array with the size equal to the range of values and count frequencies of each element. That's basically the first step of the Counting sort algorithm.
That's how it might look like. Let's assume that the range is [1,100]:
int[] arr = {5, 5, 5, 6, 7, 3, 4, 4, 4, 4, 5, 1, 2, 2, 3, 3, 5, 8, 9, 10};
int[] freq = new int[100];
final int minValue = 1; // constraint: values are in range [1, 100]
for (int next: arr) {
freq[next - minValue] ;
}
for (int i = 0; i < freq.length; i ) {
if (freq[i] > 1) System.out.print((i minValue " ").repeat(freq[i]));
}
Output:
2 2 3 3 3 4 4 4 4 5 5 5 5 5
And here's an bit advance solution using Stream API.
int[] arr = {5, 5, 5, 6, 7, 3, 4, 4, 4, 4, 5, 1, 2, 2, 3, 3, 5, 8, 9, 10};
Arrays.stream(arr)
.boxed()
.collect(Collectors.toMap(
Function.identity(), // key
i -> 1, // value
Integer::sum // resolving duplicates
))
.entrySet().stream()
.filter(e -> e.getValue() > 1) // retaining entries with duplicated keys
.forEach(e -> System.out.print((e.getKey() " ").repeat(e.getValue())));
Output:
2 2 3 3 3 4 4 4 4 5 5 5 5 5
CodePudding user response：
Using Java 8 groupingBy:
You can use the groupingBy feature by which you can easily get the frequency of each unique element present in the array,and then filter the data whose frequency is greater than 1 and iterating on this map, you can create a StringBuilder.
My approach:
I have first created a
Map<Integer,Integer> frequencyGreaterThanOne, it will hold the array element and its frequency as a key-value pair with the data whose frequency is greater than 1.TreeMap::new: It will create the sorted map.On this map
frequencyGreaterThanOne, I have iterated over it and created theStringBuilderas required.
The code as follows:
public class Test {
public static void main(String[] args) {
int[] arr = new int[] {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5,11,11,5, 5, 5, 5, 6, 7, 8, 9, 10,10,7,7};
Map<Integer,Integer> frequencyGreaterThanOne =
Arrays.stream(arr).boxed().sorted()
.collect(Collectors.groupingBy(Object::toString,Collectors.counting()))
.entrySet().stream()
.filter(x -> x.getValue() > 1)
.collect(Collectors.toMap(x -> Integer.valueOf(x.getKey()),
x -> x.getValue().intValue(),(a, b) -> a,TreeMap::new));
System.out.println(frequencyGreaterThanOne);
StringBuilder sb = new StringBuilder("");
frequencyGreaterThanOne.forEach((key, value) -> {
for (int i = 0; i < value; i ) {
sb.append(key).append(" ");
}
});
System.out.println(sb);
}
}
Output:
{2=2, 3=3, 4=4, 5=6, 7=3, 10=2, 11=2}
2 2 3 3 3 4 4 4 4 5 5 5 5 5 5 7 7 7 10 10 11 11