Как найти одинаковые строки в массиве 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.

Источник

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(n2).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

// Общий метод для проверки дубликатов в массиве

private static <T> boolean checkForDuplicates(T... array)

{

    // для каждого элемента массива проверяем, встречается ли он потом в массиве

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

    {

        for (int j = i + 1; j < array.length; j++)

        {

            if (array[i] != null && array[i].equals(array[j])) {

                return true;

            }

        }

    }

    // дубликат не найден

    return false;

}

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

// Общий метод для проверки дубликатов в массиве

private static <T> boolean checkForDuplicates(T... array)

{

    // создаем пустой набор

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

    // делаем для каждого элемента массива

    for (T e: array)

    {

        // возвращаем true, если найден дубликат

        if (set.contains(e)) {

            return true;

        }

        // вставляем текущий элемент в набор

        if (e != null) {

            set.add(e);

        }

    }

    // дубликат не найден

    return false;

}

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

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

// Общий метод для проверки дубликатов в массиве

private static <T> boolean checkForDuplicates(T... array)

{

    Set<T> set = new HashSet<>(Arrays.asList(array));

    return array.length != set.size();

}

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

// Общий метод для проверки дубликатов в массиве

private static <T> boolean checkForDuplicates(T... array)

{

    // сортируем массив в естественном или обратном порядке

    Arrays.sort(array);

    // prev сохраняет предыдущий элемент для текущего элемента в массиве

    T prev = null;

    // делаем для каждого элемента массива

    for (T e: array)

    {

        // если два последовательных элемента равны,

        // найден дубликат

        if (e != null && e.equals(prev)) {

            return true;

        }

        // устанавливаем текущий элемент как предыдущий

        prev = e;

    }

    // дубликат не найден

    return false;

}

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

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

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

// Общий метод для проверки дубликатов в массиве

private static <T> boolean checkForDuplicates(T... array)

{

    Long distinctCount = Stream.of(array).distinct().count();

    return array.length != distinctCount;

}

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

Это все о проверке дубликатов в массиве в 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);
    }
}

Заключение

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

Источник

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

Одно из решений для этого – использовать два цикла (вложенных), где внутренний цикл начинается с i + 1 (где i – переменная внешнего цикла), чтобы избежать повторений в сравнении.

Пример

import java.util.Arrays;
import java.util.Scanner;

public class DetectDuplcate {
   
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter the size of the array that is to be created::");
      int size = sc.nextInt();
      int[] myArray = new int[size];
      System.out.println("Enter the elements of the array ::");
   
      for(int i=0; i<size; i++) {
         myArray[i] = sc.nextInt();
      }
      System.out.println("The array created is ::"+Arrays.toString(myArray));
      System.out.println("indices of the duplicate elements :: ");
   
      for(int i=0; i<myArray.length; i++) {
         for (int j=i+1; j<myArray.length; j++) {
            if(myArray[i] == myArray[j]) {
               System.out.println(j);
            }
         }
      }
   }
}

Итог

Enter the size of the array that is to be created ::
6
Enter the elements of the array ::
87
52
87
63
41
63
The array created is :: [87, 52, 87, 63, 41, 63]
indices of the duplicate elements ::
2
5

Способ 2

В дополнение к этому у нас есть более надежное решение. Набор интерфейсов не позволяет дублировать элементы, поэтому создайте объект set и попробуйте добавить каждый элемент к нему с помощью метода add(), в случае повторения элементов этот метод возвращает false:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class DetectDuplcateUsingSet {
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter the size of the array that is to be created::");
      int size = sc.nextInt();
      int[] myArray = new int[size];
      System.out.println("Enter the elements of the array ::");

      for(int i=0; i<size; i++) {
         myArray[i] = sc.nextInt();
      }
      System.out.println("The array created is ::"+Arrays.toString(myArray));
      System.out.println("indices of duplicate elements in the array are elements::");
      Set set = new HashSet();
 
      for(int i=0; i<myArray.length; i++) {
         if(!set.add(myArray[i])) {
            System.out.println(i);
         }
      }
   }
}

Результат

Enter the size of the array that is to be created ::
5
Enter the elements of the array ::
78
56
23
78
45
The array created is :: [78, 56, 23, 78, 45]
indices of duplicate elements in the array are elements::
3

Источник

Понравилась статья? Поделить с друзьями:
  • Как найти мультики про лунтика
  • Как по штрих коду найти компанию
  • Астрологическое руководство как найти свою вторую половинку
  • Как найти объем фигур формулы
  • Как найти наименьшее значение квадратного выражения