Рубрики
Без рубрики

Java –Проверка если массив содержит дублированное значение

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

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

  1. Поток Java 8, сравните размер массива.
  2. Набор деревьев, сравните размер массива.
  3. Два цикла для, классический алгоритм, 0(n^2).
  4. Набор, 0(n).
  5. Растровое изображение, логическое значение[] 0(n).

Все вышеперечисленные решения тестируются с помощью приведенной ниже программы и генерируют один и тот же результат. (кроме 5. Растровое изображение)

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  boolean isDuplicate(final T[] values) {}

}

Выход

  true
  true
  false

1. Поток Java 8 – различимый() + количество()

Метод потока Java 8 distinct() извлечет все уникальные значения, а count() подсчитает общий размер. И мы можем сравнить размер, чтобы выяснить, есть ли дублированное значение в массиве.

  // Java 8 stream
  public static  boolean isDuplicate(final T[] values) {
      return Arrays.stream(values).distinct().count() != values.length;
  }

2. Набор деревьев

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

  // TreeSet will remove the duplicated values
  public static  boolean isDuplicate(final T[] values) {

      TreeSet set = new TreeSet(Arrays.asList(values));
      if (set.size() != values.length) {
          return true;
      } else {
          return false;
      }

  }

3. Два для петель

A 0(n^2) алгоритм для определения дублированных значений. Этот пример является классическим для двух циклов, чтобы определить, есть ли дублированное значение в массиве.

  // O(n^2), increase time if array size increased
  public static  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. Набор

A 0(n) алгоритм для определения дублированных значений. Зацикливает массив; если Set содержит значение, верните true для дублирования. В противном случае добавьте значение в Набор .

  // O(n), faster
  public static  boolean isDuplicate(final T[] values) {
      Set set = new HashSet();
      for (T s : values) {
          if (set.contains(s)) return true;
          set.add(s);
      }
      return false;
  }

5. Растровое изображение

A 0(n) алгоритм для определения дублированных значений. Этот пример работает только для int или Целочисленный тип, и только если мы знаем максимальный диапазон массива.

  // 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;
  }

Объяснение Предположим, что int[] находится в диапазоне от 0 до 10, и мы можем создать логическое[] с размером 10 + 1 .

  int[] values = new int[]{2, 3, 6, 4, 2, 9};
  boolean[] bitmap = new boolean[10 + 1];  // index starts at 0

Начальное значение для всех растровых изображений[0-10] равно false. (по умолчанию)

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;

цикл № 1, новый int[]{2, 3, 6, 4, 2, 9} , обновить растровое изображение[2]

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;

цикл № 2, новый int[]{2, 3, 6, 4, 2, 9} , обновить растровое изображение[3]

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;

цикл № 3, новый int[]{2, 3, 6, 4, 2, 9} , обновить растровое изображение[6]

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;

цикл № 4, новый int[]{2, 3, 6, 4, 2, 9} , обновить растровое изображение[4]

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;

цикл № 5, новый int[]{2, 3, 6, 4, 2, 9} , обновить растровое изображение[2] , подождите, растровое изображение[2] уже истинно , что означает, что этот массив содержит дублированное значение.

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;

Скачать Исходный Код

$клон git $клон git

Рекомендации

Оригинал: “https://mkyong.com/java/check-duplicated-value-in-array/”