Как найти дубликаты в массиве 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(n²).

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(n²). 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.

I did a similiar program that shows you the words that where repeated in an ArrayList (also it shows the arraylist content and the larger string)

Oh, by the way, variables, and other stuff like comments are in spanish, cause I speak spanish:/ but, if you see the code you can see that I resolved the problem with 2 bucles for!

public void mostrarDiecisiete() {


        ArrayList<String> array = new ArrayList<String>();

        ArrayList<String> array2 = new ArrayList<String>();

        Scanner sc = new Scanner(System.in);

        String sss = "";

        System.out.println("");

        while (!sss.equalsIgnoreCase("fin")) {

            System.out.print("Ingrese un string: ");
            sss = sc.nextLine();
            if (!sss.equalsIgnoreCase("fin")) {
                array.add(sss);
            }
        }

        int mayor = 0;
        Iterator it = array.iterator();
        String s = "";
        boolean repetir = true;
        int j = 0;
        for (int i = 0; i < array.size(); i++) {
            System.out.println("");
            System.out.print("Posicion: " + i + " del array: " + array.get(i) + " " + "n");

            if (array.get(i).length() > mayor) {

                mayor = array.get(i).length();

                s = array.get(i);

            }
        }

        for (int i = 0; i < array.size(); i++) {


            System.out.println("vuelta nro: " + i + " del primer for");
            if(j==array.size()){

                j=0;//inicializa de nuevo j en cero si j alcanzo el tamaño del array
                j=i;//inicializa j en el numero de vuelta del primer for, para luego sumarle uno mas asi siempre compara con el siguiente
            }
            for (j++; j < array.size(); j++) {//empieza a comparar con uno mas adelante siempre

                if (array.get(i).equalsIgnoreCase(array.get(j))) {//si el array de la posicion i se repite entre la 1 y la ultima de la pos j

                    System.out.println("el string " + array.get(i) + " se repite en la posicion " + j);

                    array2.add(array.get(i)); // se agrega a array2



                } else {
                    System.out.println("String: " + array.get(i) + " no se repite con la posicion " + j);



                }
            }

        }

        System.out.println("");

        System.out.print(
                "el array es: " + array);

        System.out.println(
                "");

        System.out.println(
                "El array mas largo es: " + s + " y tiene " + mayor + " caracteres");

        System.out.println(
                "");

        System.out.println(
                "Los Strings repetidos son" + array2);

    }

}

This is my output:

Ingrese un string: vaca
Ingrese un string: perro
Ingrese un string: dinosaurio
Ingrese un string: gato
Ingrese un string: cebra
Ingrese un string: DiNoSauRiO
Ingrese un string: VACA
Ingrese un string: hamster
Ingrese un string: gato
Ingrese un string: canario
Ingrese un string: elefante
Ingrese un string: tortuga
Ingrese un string: fin

Posicion: 0 del array: vaca 

Posicion: 1 del array: perro 

Posicion: 2 del array: dinosaurio 

Posicion: 3 del array: gato 

Posicion: 4 del array: cebra 

Posicion: 5 del array: DiNoSauRiO 

Posicion: 6 del array: VACA 

Posicion: 7 del array: hamster 

Posicion: 8 del array: gato 

Posicion: 9 del array: canario 

Posicion: 10 del array: elefante 

Posicion: 11 del array: tortuga 

vuelta nro: 0 del primer for

String: vaca no se repite con la posicion 1
String: vaca no se repite con la posicion 2
String: vaca no se repite con la posicion 3
String: vaca no se repite con la posicion 4
String: vaca no se repite con la posicion 5
el string vaca se repite en la posicion 6
String: vaca no se repite con la posicion 7
String: vaca no se repite con la posicion 8
String: vaca no se repite con la posicion 9
String: vaca no se repite con la posicion 10
String: vaca no se repite con la posicion 11
vuelta nro: 1 del primer for
String: perro no se repite con la posicion 2
String: perro no se repite con la posicion 3
String: perro no se repite con la posicion 4
String: perro no se repite con la posicion 5
String: perro no se repite con la posicion 6
String: perro no se repite con la posicion 7
String: perro no se repite con la posicion 8
String: perro no se repite con la posicion 9
String: perro no se repite con la posicion 10
String: perro no se repite con la posicion 11
vuelta nro: 2 del primer for
String: dinosaurio no se repite con la posicion 3
String: dinosaurio no se repite con la posicion 4
el string dinosaurio se repite en la posicion 5
String: dinosaurio no se repite con la posicion 6
String: dinosaurio no se repite con la posicion 7
String: dinosaurio no se repite con la posicion 8
String: dinosaurio no se repite con la posicion 9
String: dinosaurio no se repite con la posicion 10
String: dinosaurio no se repite con la posicion 11
vuelta nro: 3 del primer for
String: gato no se repite con la posicion 4
String: gato no se repite con la posicion 5
String: gato no se repite con la posicion 6
String: gato no se repite con la posicion 7
el string gato se repite en la posicion 8
String: gato no se repite con la posicion 9
String: gato no se repite con la posicion 10
String: gato no se repite con la posicion 11
vuelta nro: 4 del primer for
String: cebra no se repite con la posicion 5
String: cebra no se repite con la posicion 6
String: cebra no se repite con la posicion 7
String: cebra no se repite con la posicion 8
String: cebra no se repite con la posicion 9
String: cebra no se repite con la posicion 10
String: cebra no se repite con la posicion 11
vuelta nro: 5 del primer for
String: DiNoSauRiO no se repite con la posicion 6
String: DiNoSauRiO no se repite con la posicion 7
String: DiNoSauRiO no se repite con la posicion 8
String: DiNoSauRiO no se repite con la posicion 9
String: DiNoSauRiO no se repite con la posicion 10
String: DiNoSauRiO no se repite con la posicion 11
vuelta nro: 6 del primer for
String: VACA no se repite con la posicion 7
String: VACA no se repite con la posicion 8
String: VACA no se repite con la posicion 9
String: VACA no se repite con la posicion 10
String: VACA no se repite con la posicion 11
vuelta nro: 7 del primer for
String: hamster no se repite con la posicion 8
String: hamster no se repite con la posicion 9
String: hamster no se repite con la posicion 10
String: hamster no se repite con la posicion 11
vuelta nro: 8 del primer for
String: gato no se repite con la posicion 9
String: gato no se repite con la posicion 10
String: gato no se repite con la posicion 11
vuelta nro: 9 del primer for
String: canario no se repite con la posicion 10
String: canario no se repite con la posicion 11
vuelta nro: 10 del primer for
String: elefante no se repite con la posicion 11
vuelta nro: 11 del primer for

el array es: [vaca, perro, dinosaurio, gato, cebra, DiNoSauRiO, VACA, hamster, gato, canario, elefante, tortuga]

El array mas largo es: dinosaurio y tiene 10 caracteres

Los Strings repetidos son[vaca, dinosaurio, gato]  

BUILD SUCCESSFUL (total time: 2 minutes 48 seconds)

В этом посте будет обсуждаться, как проверить наличие дубликатов в массиве в Java.

1. Наивное решение

Наивное решение — проверять, повторяется ли каждый элемент массива или не использовать вложенные циклы for. Временная сложность этого решения будет O(n²).

Скачать  Выполнить код

2. Использование HashSet

Мы можем работать лучше, используя Хеширование. Идея состоит в том, чтобы пройти по заданному массиву и вставить каждый встреченный элемент в HashSet. Теперь, если встреченный элемент уже присутствовал в наборе, он является дубликатом. Временная сложность этого решения O(n) но вспомогательное пространство используется O(n).

Скачать  Выполнить код

Мы знаем это HashSet не допускает дублирования значений в нем. Мы можем использовать это свойство для проверки дубликатов в массиве. Идея состоит в том, чтобы вставить все элементы массива в HashSet. Теперь массив содержит дубликат, если длина массива не равна размеру набора.

Скачать  Выполнить код

3. Использование сортировки

Идея состоит в том, чтобы отсортировать массив в естественном или обратном порядке. Теперь проходим по массиву и сравниваем соседние элементы. Если какой-либо соседний элемент окажется одинаковым, мы можем сказать, что массив содержит дубликат. Временная сложность этого решения O(n.log(n)).

Скачать  Выполнить код

4. Использование Java 8

В Java 8 мы можем использовать потоки для подсчета различных элементов, присутствующих в массиве. Если число уникальных элементов не совпадает с длиной массива, массив содержит дубликат.

Скачать  Выполнить код

Это все о проверке дубликатов в массиве в Java.

Иногда возникает необходимость найти дубликаты в массиве. В данной статье мы расскажем, как это сделать двумя способами.

Задача

Итак, у нас есть массив. Это может быть массив любых объектов или примитивов. Для примера возьмём массив строк:

String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

Теперь попробуем найти дублирующиеся строки в этом массиве.

Поиск дубликатов перебором

Сначала объявим вспомогательную коллекцию для хранения дубликатов – HashSet:

Set<T> duplicates = new HashSet<>();

Каждый раз, находя дубликат в массиве, мы будет его класть в данный HashSet.

Далее мы будем проходить по элементам массива, используя два цикла. В первом цикле мы извлекаем элемент массива и поочерёдно сравниваем его с остальными элементами массива, используя второй цикл:

for (int i = 0; i < a.length; i++) {
    T e1 = a[i];
    if (e1 == null) continue; // игнорируем null

    // сравниваем каждый элемент со всеми остальными
    for (int j = 0; j < a.length; j++) {
        if (i == j) continue; // не проверяем элемент с собой же
        T e2 = a[j];
        if (e1.equals(e2)) {
            // дубликат найден, сохраним его
            duplicates.add(e2);
        }
    }
}

И в конце возвратим найденные дубликаты:

return new ArrayList<>(duplicates);

Проверка

Проверим нашу программу:

String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

System.out.println("Входной массив: " + Arrays.toString(animals));
System.out.println("Дубликаты: " + getDuplicatesWithIteration(animals));

Исходный код

package ru.javalessons.arrays;

import java.util.*;

public class ArrayFindDuplicates {
    public static void main(String[] args) {
        String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

        System.out.println("Входной массив: " + Arrays.toString(animals));
        System.out.println("Дубликаты: " + getDuplicatesWithIteration(animals));
    }

    public static <T> List<T> getDuplicatesWithIteration(T[] a) {
        Set<T> duplicates = new HashSet<>();
        for (int i = 0; i < a.length; i++) {
            T e1 = a[i];
            if (e1 == null) continue; // игнорируем null

            // сравниваем каждый элемент со всеми остальными
            for (int j = 0; j < a.length; j++) {
                if (i == j) continue; // не проверяем элемент с собой же
                T e2 = a[j];
                if (e1.equals(e2)) {
                    // дубликат найден, сохраним его
                    duplicates.add(e2);
                }
            }
        }
        return new ArrayList<>(duplicates);
    }
}

Заключение

На данном примере мы разобрали, как находить дубликаты в массиве. Это может быть массив любых объектов.

There are multiple ways to find duplicate elements in an array in Java and we will see three of them in this program. The solution and logic shown in this article are generic and apply to an array of any type e.g. String array or integer array or array of any object. One of the most common ways to find duplicates is by using the brute force method, which compares each element of the array to every other element. This solution has the time complexity of O(n^2) and only exists for academic purposes. You shouldn’t be using this solution in the real world.

The standard way to find duplicate elements from an array is by using the HashSet data structure. If you remember, Set abstract data type doesn’t allow duplicates. You can take advantage of this property to filter duplicate elements.

This solution has a time complexity of O(n), as you only need to iterate over array once, but also has a space complexity of O(n) as you need to store unique elements in the array.

Our third solution to find duplicate elements in an array is actually similar to our second solution but instead of using a Set data structure, we will use the hash table data structure. This is a pretty good solution because you can extend it to the found count of duplicates as well. In this solution, we iterate over the array and build the map which stores array elements and their count.

Once the table is built, you can iterate over a hash table and print out all the elements, who have a count greater than one, those are your duplicates.

Also, basic knowledge of essential data structure is also very important and that’s why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

How to find duplicates in Java array?

In the first paragraph, I have given you a brief overview of three ways to find duplicate elements from Java array. Now, let’s understand the logic behind each of those solutions in little more detail.

Solution 1 :

Our first solution is very simple. All we are doing here is to loop over an array and comparing each element to every other element. For doing this, we are using two loops, inner loop, and outer loop. We are also making sure that we are ignoring comparing of elements to itself by checking for i != j before printing duplicates. Since we are comparing every element to every other element, this solution has quadratic time complexity i.e. O(n^2). This solution has the worst complexity in all three solutions.

 for (int i = 0; i < names.length; i++) {
     for (int j = i + 1 ; j < names.length; j++) {
          if (names[i].equals(names[j])) {
                   // got the duplicate element
          }
     }
 }

This question is also very popular in programming interviews and if you are preparing for them, I also suggest you solve problems from Cracking the Coding Interview: 150 Programming Questions and Solutions. One of the best books to prepare for software developer interviews.

Solution 2 :

The second solution is even simpler than this. All you need to know is that Set doesn’t allow duplicates in Java. Which means if you have added an element into Set and trying to insert duplicate element again, it will not be allowed. In Java, you can use the HashSet class to solve this problem. Just loop over array elements, insert them into HashSet using add() method, and check the return value.

If add() returns false it means that element is not allowed in the Set and that is your duplicate. Here is the code sample to do this :

 for (String name : names) {
     if (set.add(name) == false) {
        // your duplicate element
     }
}

The complexity of this solution is O(n) because you are only going through the array one time, but it also has a space complexity of O(n) because of the HashSet data structure, which contains your unique elements. So if an array contains 1 million elements, in the worst case you would need a HashSet to store those 1 million elements.

Solution 3 :

Our third solution takes advantage of another useful data structure, hash table. All you need to do is loop through the array using enhanced for loop and insert each element and its count into hash table. You can use HashMap class of JDK to solve this problem. It is the general purpose hash table implementation in Java. In order to build table, you check if hash table contains the elements or not, if it is then increment the count otherwise insert element with count 1. Once you have this table ready, you can iterate over hashtable and print all those keys which has values greater than one. These are your duplicate elements. This is in fact a very good solution because you can extend it to found count of duplicates as well. If you remember, I have used this approach to find duplicate characters in String earlier. Here is how you code will look like :

// build hash table with count
        for (String name : names) {
            Integer count = nameAndCount.get(name);
            if (count == null) {
                nameAndCount.put(name, 1);
            } else {
                nameAndCount.put(name, ++count);
            }
        }

        // Print duplicate elements from array in Java
        Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet();
        for (Entry<String, Integer> entry : entrySet) {
            if (entry.getValue() > 1) {
                System.out.printf("duplicate element '%s' and count '%d' :", entry.getKey(), entry.getValue());
            }
        }

Time complexity of this solution is O(2n) because we are iterating over array twice and space complexity is same as previous solution O(n). In worst case you would need a hash table with size of array itself.

Java Program to find duplicate elements in array

Here is our three solutions packed into a Java program to find duplicate elements in array. You can run this example from command line or Eclipse IDE, whatever suits you. Just make sure that name of your Java source file should be same as your public class e.g. “DuplicatesInArray”. I have left bit of exercise for you, of course if you would like to do. Can you refactor this code into methods, you can do that easily by using extract method feature of IDE like Eclipse and Netbans and write unit test to check the logic of each approach. This would give you some practice in refactoring code and writing JUnit tests, two important attributes of a professional programmer.

package dto;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Java Program to find duplicate elements in an array. There are two straight
 * forward solution of this problem first, brute force way and second by using
 * HashSet data structure. A third solution, similar to second one is by using
 * hash table data structure e.g. HashMap to store count of each element and
 * print element with count 1.
 * 
 * @author java67
 */

public class DuplicatesInArray{

    public static void main(String args[]) {

        String[] names = { "Java", "JavaScript", "Python", "C", "Ruby", "Java" };

        // First solution : finding duplicates using brute force method
        System.out.println("Finding duplicate elements in array using brute force method");
        for (int i = 0; i < names.length; i++) {
            for (int j = i + 1; j < names.length; j++) {
                if (names[i].equals(names[j]) ) {
                   // got the duplicate element
                }
            }
        }

        // Second solution : use HashSet data structure to find duplicates
        System.out.println("Duplicate elements from array using HashSet data structure");
        Set<String> store = new HashSet<>();

        for (String name : names) {
            if (store.add(name) == false) {
                System.out.println("found a duplicate element in array : "
                        + name);
            }
        }

        // Third solution : using Hash table data structure to find duplicates
        System.out.println("Duplicate elements from array using hash table");
        Map<String, Integer> nameAndCount = new HashMap<>();

        // build hash table with count
        for (String name : names) {
            Integer count = nameAndCount.get(name);
            if (count == null) {
                nameAndCount.put(name, 1);
            } else {
                nameAndCount.put(name, ++count);
            }
        }

        // Print duplicate elements from array in Java
        Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet();
        for (Entry<String, Integer> entry : entrySet) {

            if (entry.getValue() > 1) {
                System.out.println("Duplicate element from array : "
                        + entry.getKey());
            }
        }
    }
}
Output :
Finding duplicate elements in array using brute force method
Duplicate elements from array using HashSet data structure
found a duplicate element in array : Java
Duplicate elements from array using hash table
Duplicate element from array : Java

From the output, you can see that the only duplicate element from our String array, which is “Java” has been found by all of our three solutions.

That’s all about how to find duplicate elements in an array in Java. In this tutorial, you have learned three ways to solve this problem. The brute force way require you to compare each element from array to another, hence has quadratic time complexity. You can optimize performance by using HashSet data structure, which doesn’t allow duplicates. So a duplicate element is the one for which add() method of HashSet return false. Our third solution uses hash table data structure to make a table of elements and their count. Once you build that table, iterate over it and print elements whose count is greater than one. This is a very good coding problem and frequently asked in Java Interview. It also shows how use of a right data structure can improve performance of algorithm significantly.

If you have like this coding problem, you may also like to solve following coding problems from Java Interviews :

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures – Part 1 and 2

Recommended books to Prepare for Software Engineer Interviews

If you are solving these coding problems to prepare for software engineer job interviews, you can also take a look at following books. They contain wealth of knowledge and several frequently asked coding problems from Java and C++ interviews :