Java Array, Finding Duplicates
JavaArraysJava Problem Overview
I have an array, and am looking for duplicates.
duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
for(k = 0; k < zipcodeList.length; k++){
if (zipcodeList[k] == zipcodeList[j]){
duplicates = true;
}
}
}
However, this code doesnt work when there are no duplicates. Whys that?
Java Solutions
Solution 1 - Java
On the nose answer..
duplicates=false;
for (j=0;j<zipcodeList.length;j++)
for (k=j+1;k<zipcodeList.length;k++)
if (k!=j && zipcodeList[k] == zipcodeList[j])
duplicates=true;
Edited to switch .equals() back to == since I read somewhere you're using int, which wasn't clear in the initial question. Also to set k=j+1, to halve execution time, but it's still O(n2).
A faster (in the limit) way
Here's a hash based approach. You gotta pay for the autoboxing, but it's O(n) instead of O(n2). An enterprising soul would go find a primitive int-based hash set (Apache or Google Collections has such a thing, methinks.)
boolean duplicates(final int[] zipcodelist)
{
Set<Integer> lump = new HashSet<Integer>();
for (int i : zipcodelist)
{
if (lump.contains(i)) return true;
lump.add(i);
}
return false;
}
Bow to HuyLe
See HuyLe's answer for a more or less O(n) solution, which I think needs a couple of add'l steps:
static boolean duplicates(final int[] zipcodelist)
{
final int MAXZIP = 99999;
boolean[] bitmap = new boolean[MAXZIP+1];
java.util.Arrays.fill(bitmap, false);
for (int item : zipcodeList)
if (!bitmap[item]) bitmap[item] = true;
else return true;
}
return false;
}
Or Just to be Compact
static boolean duplicates(final int[] zipcodelist)
{
final int MAXZIP = 99999;
boolean[] bitmap = new boolean[MAXZIP+1]; // Java guarantees init to false
for (int item : zipcodeList)
if (!(bitmap[item] ^= true)) return true;
return false;
}
Does it Matter?
Well, so I ran a little benchmark, which is iffy all over the place, but here's the code:
import java.util.BitSet;
class Yuk
{
static boolean duplicatesZero(final int[] zipcodelist)
{
boolean duplicates=false;
for (int j=0;j<zipcodelist.length;j++)
for (int k=j+1;k<zipcodelist.length;k++)
if (k!=j && zipcodelist[k] == zipcodelist[j])
duplicates=true;
return duplicates;
}
static boolean duplicatesOne(final int[] zipcodelist)
{
final int MAXZIP = 99999;
boolean[] bitmap = new boolean[MAXZIP + 1];
java.util.Arrays.fill(bitmap, false);
for (int item : zipcodelist) {
if (!(bitmap[item] ^= true))
return true;
}
return false;
}
static boolean duplicatesTwo(final int[] zipcodelist)
{
final int MAXZIP = 99999;
BitSet b = new BitSet(MAXZIP + 1);
b.set(0, MAXZIP, false);
for (int item : zipcodelist) {
if (!b.get(item)) {
b.set(item, true);
} else
return true;
}
return false;
}
enum ApproachT { NSQUARED, HASHSET, BITSET};
/**
* @param args
*/
public static void main(String[] args)
{
ApproachT approach = ApproachT.BITSET;
final int REPS = 100;
final int MAXZIP = 99999;
int[] sizes = new int[] { 10, 1000, 10000, 100000, 1000000 };
long[][] times = new long[sizes.length][REPS];
boolean tossme = false;
for (int sizei = 0; sizei < sizes.length; sizei++) {
System.err.println("Trial for zipcodelist size= "+sizes[sizei]);
for (int rep = 0; rep < REPS; rep++) {
int[] zipcodelist = new int[sizes[sizei]];
for (int i = 0; i < zipcodelist.length; i++) {
zipcodelist[i] = (int) (Math.random() * (MAXZIP + 1));
}
long begin = System.currentTimeMillis();
switch (approach) {
case NSQUARED :
tossme ^= (duplicatesZero(zipcodelist));
break;
case HASHSET :
tossme ^= (duplicatesOne(zipcodelist));
break;
case BITSET :
tossme ^= (duplicatesTwo(zipcodelist));
break;
}
long end = System.currentTimeMillis();
times[sizei][rep] = end - begin;
}
long avg = 0;
for (int rep = 0; rep < REPS; rep++) {
avg += times[sizei][rep];
}
System.err.println("Size=" + sizes[sizei] + ", avg time = "
+ avg / (double)REPS + "ms");
}
}
}
With NSQUARED:
Trial for size= 10
Size=10, avg time = 0.0ms
Trial for size= 1000
Size=1000, avg time = 0.0ms
Trial for size= 10000
Size=10000, avg time = 100.0ms
Trial for size= 100000
Size=100000, avg time = 9923.3ms
With HashSet
Trial for zipcodelist size= 10
Size=10, avg time = 0.16ms
Trial for zipcodelist size= 1000
Size=1000, avg time = 0.15ms
Trial for zipcodelist size= 10000
Size=10000, avg time = 0.0ms
Trial for zipcodelist size= 100000
Size=100000, avg time = 0.16ms
Trial for zipcodelist size= 1000000
Size=1000000, avg time = 0.0ms
With BitSet
Trial for zipcodelist size= 10
Size=10, avg time = 0.0ms
Trial for zipcodelist size= 1000
Size=1000, avg time = 0.0ms
Trial for zipcodelist size= 10000
Size=10000, avg time = 0.0ms
Trial for zipcodelist size= 100000
Size=100000, avg time = 0.0ms
Trial for zipcodelist size= 1000000
Size=1000000, avg time = 0.0ms
BITSET Wins!
But only by a hair... .15ms is within the error for currentTimeMillis(), and there are some gaping holes in my benchmark. Note that for any list longer than 100000, you can simply return true because there will be a duplicate. In fact, if the list is anything like random, you can return true WHP for a much shorter list. What's the moral? In the limit, the most efficient implementation is:
return true;
And you won't be wrong very often.
Solution 2 - Java
Let's see how your algorithm works:
an array of unique values:
[1, 2, 3]
check 1 == 1. yes, there is duplicate, assigning duplicate to true.
check 1 == 2. no, doing nothing.
check 1 == 3. no, doing nothing.
check 2 == 1. no, doing nothing.
check 2 == 2. yes, there is duplicate, assigning duplicate to true.
check 2 == 3. no, doing nothing.
check 3 == 1. no, doing nothing.
check 3 == 2. no, doing nothing.
check 3 == 3. yes, there is duplicate, assigning duplicate to true.
a better algorithm:
for (j=0;j<zipcodeList.length;j++) {
for (k=j+1;k<zipcodeList.length;k++) {
if (zipcodeList[k]==zipcodeList[j]){ // or use .equals()
return true;
}
}
}
return false;
Solution 3 - Java
You can use bitmap for better performance with large array.
java.util.Arrays.fill(bitmap, false);
for (int item : zipcodeList)
if (!bitmap[item]) bitmap[item] = true;
else break;
UPDATE: This is a very negligent answer of mine back in the day, keeping it here just for reference. You should refer to andersoj's excellent answer.
Solution 4 - Java
To check for duplicates you need to compare distinct pairs.
Solution 5 - Java
Cause you are comparing the first element of the array against itself so It finds that there are duplicates even where there aren't.
Solution 6 - Java
Initialize k = j+1. You won't compare elements to themselves and you'll also not duplicate comparisons. For example, j = 0, k = 1 and k = 0, j = 1 compare the same set of elements. This would remove the k = 0, j = 1 comparison.
Solution 7 - Java
You can also work with Set, which doesn't allow duplicates in Java..
for (String name : names)
{
if (set.add(name) == false)
{ // your duplicate element }
}
using add() method and check return value. If add() returns false it means that element is not allowed in the Set and that is your duplicate.
Solution 8 - Java
Don't use == use .equals.
try this instead (IIRC, ZipCode needs to implement Comparable for this to work.
boolean unique;
Set<ZipCode> s = new TreeSet<ZipCode>();
for( ZipCode zc : zipcodelist )
unique||=s.add(zc);
duplicates = !unique;
Solution 9 - Java
public static ArrayList<Integer> duplicate(final int[] zipcodelist) {
HashSet<Integer> hs = new HashSet<>();
ArrayList<Integer> al = new ArrayList<>();
for(int element: zipcodelist) {
if(hs.add(element)==false) {
al.add(element);
}
}
return al;
}
Solution 10 - Java
How about using this method?
HashSet<Integer> zipcodeSet = new HashSet<Integer>(Arrays.asList(zipcodeList));
duplicates = zipcodeSet.size()!=zipcodeList.length;
Solution 11 - Java
@andersoj gave a great answer, but I also want add new simple way
private boolean checkDuplicateBySet(Integer[] zipcodeList) {
Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeList));
if (zipcodeSet.size() == zipcodeList.length) {
return true;
}
return false;
}
In case zipcodeList is int[], you need convert int[] to Integer[] first(It not auto-boxing), code here
Complete code will be:
private boolean checkDuplicateBySet2(int[] zipcodeList) {
Integer[] zipcodeIntegerArray = new Integer[zipcodeList.length];
for (int i = 0; i < zipcodeList.length; i++) {
zipcodeIntegerArray[i] = Integer.valueOf(zipcodeList[i]);
}
Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeIntegerArray));
if (zipcodeSet.size() == zipcodeList.length) {
return true;
}
return false;
}
Hope this helps!
Solution 12 - Java
Print all the duplicate elements. Output -1 when no repeating elements are found.
import java.util.*;
public class PrintDuplicate {
public static void main(String args[]){
HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
Scanner s=new Scanner(System.in);
int ii=s.nextInt();
int k=s.nextInt();
int[] arr=new int[k];
int[] arr1=new int[k];
int l=0;
for(int i=0; i<arr.length; i++)
arr[i]=s.nextInt();
for(int i=0; i<arr.length; i++){
if(h.containsKey(arr[i])){
h.put(arr[i], h.get(arr[i]) + 1);
arr1[l++]=arr[i];
} else {
h.put(arr[i], 1);
}
}
if(l>0)
{
for(int i=0;i<l;i++)
System.out.println(arr1[i]);
}
else
System.out.println(-1);
}
}
Solution 13 - Java
import java.util.Scanner;
public class Duplicates {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int number = console.nextInt();
String numb = "" + number;
int leng = numb.length()-1;
if (numb.charAt(0) != numb.charAt(1)) {
System.out.print(numb.substring(0,1));
}
for (int i = 0; i < leng; i++){
if (numb.charAt(i)==numb.charAt(i+1)){
System.out.print(numb.substring(i,i+1));
}
else {
System.out.print(numb.substring(i+1,i+2));
}
}
}
}
Solution 14 - Java
> This program will print all duplicates value from array.
public static void main(String[] args) {
int[] array = new int[] { -1, 3, 4, 4,4,3, 9,-1, 5,5,5, 5 };
Arrays.sort(array);
boolean isMatched = false;
int lstMatch =-1;
for(int i = 0; i < array.length; i++) {
try {
if(array[i] == array[i+1]) {
isMatched = true;
lstMatch = array[i+1];
}
else if(isMatched) {
System.out.println(lstMatch);
isMatched = false;
lstMatch = -1;
}
}catch(Exception ex) {
//TODO NA
}
}
if(isMatched) {
System.out.println(lstMatch);
}
}
}
Solution 15 - Java
public static void findDuplicates(List<Integer> list){
if(list!=null && !list.isEmpty()){
Set<Integer> uniques = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
for(int i=0;i<list.size();i++){
if(!uniques.add(list.get(i))){
duplicates.add(list.get(i));
}
}
System.out.println("Uniques: "+uniques);
System.out.println("Duplicates: "+duplicates);
}else{
System.out.println("LIST IS INVALID");
}
}
Solution 16 - Java
public static <T> Set<T> getDuplicates(Collection<T> array) {
Set<T> duplicateItem = new HashSet<>();
Iterator<T> it = array.iterator();
while(it.hasNext()) {
T object = it.next();
if (Collections.frequency(array, object) > 1) {
duplicateItem.add(object);
it.remove();
}
}
return duplicateItem;
}
// Otherway if you dont need to sort your collection, you can use this way.
public static <T> List<T> getDuplicates(Collection<T> array) {
List<T> duplicateItem = new ArrayList<>();
Iterator<T> it = array.iterator();
while(it.hasNext()) {
T object = it.next();
if (Collections.frequency(array, object) > 1) {
if (Collections.frequency(duplicateItem, object) < 1) {
duplicateItem.add(object);
}
it.remove();
}
}
return duplicateItem;
}