В этой статье показано несколько способов определить, содержит ли массив дублированное значение.
- Поток Java 8, сравните размер массива.
- Набор деревьев, сравните размер массива.
- Два цикла для, классический алгоритм, 0(n^2).
- Набор, 0(n).
- Растровое изображение, логическое значение[] 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 staticboolean isDuplicate(final T[] values) {} }
Выход
true true false
1. Поток Java 8 – различимый() + количество()
Метод потока Java 8 distinct()
извлечет все уникальные значения, а count()
подсчитает общий размер. И мы можем сравнить размер, чтобы выяснить, есть ли дублированное значение в массиве.
// Java 8 stream public staticboolean isDuplicate(final T[] values) { return Arrays.stream(values).distinct().count() != values.length; }
2. Набор деревьев
Этот пример похож на приведенное выше решение для потоковой передачи. Набор деревьев
автоматически удалит дублированные значения, и мы сможем сравнить размер, чтобы выяснить, есть ли дублированное значение в массиве.
// TreeSet will remove the duplicated values public staticboolean 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 staticboolean 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 staticboolean 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/”