Java – Check if array contains duplicated value
This article shows a few ways to detect if an array contains a duplicated value.
- Java 8 Stream, compare the array size.
- TreeSet, compare the array size.
- Two for loops, classic algorithm, 0(n^2).
- Set, 0(n).
- Bitmap, boolean[] 0(n).
All the above solutions are tested with the below program and generate the same output. (except 5. Bitmap)
package com.mkyong.basic;
import java.util.Arrays;
public class CheckDuplicateArray {
public static void main(String args[]) {
String[] sValueDuplicated = new String[]{"a", "b", "c", "d", "1", "e", "f", "1", "4", "z"};
Integer[] iValueDuplicated = new Integer[]{2, 3, 1, 4, 99, 2, 9, 7, 88, 2};
Integer[] iValuesUnique = new Integer[]{2, 3, 1, 4, 99, 5, 6, 7, 88, 9};
System.out.println(isDuplicate(sValueDuplicated)); // true
System.out.println(isDuplicate(iValueDuplicated)); // true
System.out.println(isDuplicate(iValuesUnique)); // false
}
// public static <T> boolean isDuplicate(final T[] values) {}
}
Output
true
true
false
1. Java 8 Stream – distinct() + count()
The Java 8 stream’s distinct()
method will extract all the unique values, and the count()
will count the total size. And we can compare the size to find out if there is a duplicated value in an array.
// Java 8 stream
public static <T> boolean isDuplicate(final T[] values) {
return Arrays.stream(values).distinct().count() != values.length;
}
2. TreeSet
This example is similar to the above stream distinct solution. The TreeSet
will automatically remove the duplicated values, and we can compare the size to find out if there is a duplicated value in an array.
// TreeSet will remove the duplicated values
public static <T> boolean isDuplicate(final T[] values) {
TreeSet set = new TreeSet<T>(Arrays.asList(values));
if (set.size() != values.length) {
return true;
} else {
return false;
}
}
3. Two for loops
A 0(n^2)
algorithm to find out the duplicated values. This example is a classic two for loops to determine if there is a duplicated value in an array.
// O(n^2), increase time if array size increased
public static <T> boolean isDuplicate(final T[] values) {
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < values.length; j++) {
if (i == j) continue; //same index position, ignore
if (values instanceof String[]) {
if (values[i].equals(values[j])) {
return true;
}
} else {
if (values[i] == values[j]) {
return true;
}
}
}
}
return false;
}
4. Set
A 0(n)
algorithm to find out the duplicated values. Loops the array; if the Set
contains the value, return true for duplication. Otherwise, add the value to the Set
.
// O(n), faster
public static <T> boolean isDuplicate(final T[] values) {
Set set = new HashSet<T>();
for (T s : values) {
if (set.contains(s)) return true;
set.add(s);
}
return false;
}
5. Bitmap
A 0(n)
algorithm to find out the duplicated values. This example only works for int
or Integer
type, and only if we know the max range of an array.
// O(n), if you know the max range, try this, super fast
public static boolean isDuplicate(final int[] values) {
// range from 0 - 9999 + 1
final int max = 9999;
boolean[] bitmap = new boolean[max + 1];
for (int item : values) {
if (bitmap[item]) {
return true;
} else {
bitmap[item] = true;
}
}
return false;
}
Explanation
Assume the int[]
is from range 0 to 10, and we can create a boolean[]
with a size of 10 + 1
.
int[] values = new int[]{2, 3, 6, 4, 2, 9};
boolean[] bitmap = new boolean[10 + 1]; // index starts at 0
Initial all bitmap[0-10]
to false. (default)
bitmap[0] = false;
bitmap[1] = false;
bitmap[2] = false;
bitmap[3] = false;
bitmap[4] = false;
bitmap[5] = false;
bitmap[6] = false;
bitmap[7] = false;
bitmap[8] = false;
bitmap[9] = false;
bitmap[10] = false;
loop #1, new int[]{2, 3, 6, 4, 2, 9}
, update bitmap[2] = true
bitmap[0] = false;
bitmap[1] = false;
bitmap[2] = true;
bitmap[3] = false;
bitmap[4] = false;
bitmap[5] = false;
bitmap[6] = false;
bitmap[7] = false;
bitmap[8] = false;
bitmap[9] = false;
bitmap[10] = false;
loop #2, new int[]{2, 3, 6, 4, 2, 9}
, update bitmap[3] = true
bitmap[0] = false;
bitmap[1] = false;
bitmap[2] = true;
bitmap[3] = true;
bitmap[4] = false;
bitmap[5] = false;
bitmap[6] = false;
bitmap[7] = false;
bitmap[8] = false;
bitmap[9] = false;
bitmap[10] = false;
loop #3, new int[]{2, 3, 6, 4, 2, 9}
, update bitmap[6] = true
bitmap[0] = false;
bitmap[1] = false;
bitmap[2] = true;
bitmap[3] = true;
bitmap[4] = false;
bitmap[5] = false;
bitmap[6] = true;
bitmap[7] = false;
bitmap[8] = false;
bitmap[9] = false;
bitmap[10] = false;
loop #4, new int[]{2, 3, 6, 4, 2, 9}
, update bitmap[4] = true
bitmap[0] = false;
bitmap[1] = false;
bitmap[2] = true;
bitmap[3] = true;
bitmap[4] = true;
bitmap[5] = false;
bitmap[6] = true;
bitmap[7] = false;
bitmap[8] = false;
bitmap[9] = false;
bitmap[10] = false;
loop #5, new int[]{2, 3, 6, 4, 2, 9}
, update bitmap[2] = true
, wait, the bitmap[2]
is already true
, meaning this array contains duplicated value.
bitmap[0] = false;
bitmap[1] = false;
bitmap[2] = true;
bitmap[3] = true;
bitmap[4] = true;
bitmap[5] = false;
bitmap[6] = true;
bitmap[7] = false;
bitmap[8] = false;
bitmap[9] = false;
bitmap[10] = false;
Download Source Code
$ git clone https://github.com/mkyong/core-java