У меня есть два массива String, скажем:
String[] s1 = {"a","b","c"}
String[] s2 = {"c","a","b"}
//эти массивы должны быть равны
Я хотел проверить их равенство "самым чистым" способом.
Я попытался использовать Arrays.equals(s1,s2), но я получаю ложный ответ. Я предполагаю, что этот метод касается порядка элементов, и я не хочу, чтобы это имело значение.
Не могли бы вы рассказать мне, как я могу сделать это красиво?
Если вы не хотите изменять исходные массивы
Arrays.equals( Arrays.sort( Arrays.copyof(s1,s1.length)),
Arrays.sort( Arrays.copyof(s2,s2.length)) );
Arrays.sort() использует оптимизированную быструю сортировку, которая является nlog (n) для среднего, но O (n2) в худшем случае. Из java-документов. Поэтому в худшем случае O (n2), но в большинстве случаев это будет O (nlogn).
Алгоритм сортировки - это настроенная быстродействующая сортировка, адаптированная из Jon L. Bentley и M. Douglas McIlroy "Engineering a Sort Function", Software-Practice and Experience, Vol. 23 (11), с. 1249-1265 (ноябрь 1993 года). Этот алгоритм обеспечивает производительность n * log (n) на многих наборах данных, которые приводят к снижению производительности в быстродействующих секторах до квадратичной производительности.
Другие предложили сортировать массивы. Но так как вы ищете "самое чистое" решение, я думаю, что оригинальные массивы не следует трогать. Следовательно:
List<String> l1 = new ArrayList<String>(Arrays.asList(s1));
List<String> l2 = new ArrayList<String>(Arrays.asList(s2));
Collections.sort(l1);
Collections.sort(l2);
boolean outcome = l1.equals(l2);
String[] s1 = {"a","b","c"};
String[] s2 = {"b","c","a"} ;
Arrays.sort(s1);
Arrays.sort(s2);
if(Arrays.equals(s1, s2)){
System.out.println("ok");
}
Если вы используете Коллекции Eclipse (ранее Коллекции GS), вы можете использовать Bag, чтобы выяснить, равны ли эти два массива.
String[] s1 = {"a", "b", "c", "c"};
String[] s2 = {"c", "a", "b", "c"};
Bag<String> h1 = HashBag.newBagWith(s1);
Bag<String> h2 = HashBag.newBagWith(s2);
Assert.assertEquals(h1, h2);
Сумки (также известные как мультимножества) считаются равными, если они имеют одинаковое количество вхождений каждого элемента. Заказ не имеет значения, и он правильно обрабатывает повторяющиеся элементы. Преимущество использования мешка, поддерживаемого хеш-таблицей, заключается в том, что создание занимает линейное время. Сортировка и принимает O (n log n).
Примечание: я являюсь коммиттером для коллекций Eclipse
Человеческий путь:
Итерации по первому массиву, проверка наличия каждого элемента во втором массиве, а затем выполнение этого же для второго массива в первом массиве. Время: n ^ 2. Обратите внимание, что этот метод предполагает, что ни один элемент не повторяется. Если бы это было так, вам нужно было бы для каждого элемента, который вы проверяете, вернуться к началу и подсчитать, сколько экземпляров этого элемента есть (скажем, X), и только считать успехом, как найти X-й элемент в второй массив. Это позволит устранить необходимость второй проверки и оставить упражнение для читателя (если вы так склонны, то есть.)
boolean equal(String[] arr1, String[] arr2) {
if(arr1.length != arr2.length) return false; // obviously
main_loop:
for(int i = 0; i < arr1.length; i++) {
for(int j = 0; j < arr2.length; j++) {
if(arr1[i].equals(arr2[j]))
break main_loop;
}
return false;
}
main_loop:
for(int i = 0; i < arr2.length; i++) {
for(int j = 0; j < arr1.length; j++) {
if(arr2[i].equals(arr1[j]))
break main_loop;
}
return false;
}
// having got through both loops, we can now return true
}
Более продвинутый способ: сортировать оба массива и перемещаться по ним. Время: n lg n
boolean equals(String[] arr1, String[] arr2) {
if(arr1.length != arr2.length) return false;
String[] copy1 = Arrays.copyOf(arr1,arr1.length); // java.util.Arrays
String[] copy2 = Arrays.copyOf(arr2,arr2.length); // java.util.Arrays
Arrays.sort(copy1);
Arrays.sort(copy2);
for(int i = 0; i < copy1.length; i++) {
if(!copy1[i].equals(copy2[i])
return false;
}
return true;
}
Еще более продвинутый способ: использовать hashmap, добавляя для счетчиков первого массива строк, удаляя для счетчиков второго массива строк. Когда вы все равно, все значения должны быть равны нулю.
boolean equal(String[] arr1, String[] arr2) {
if(arr1.length != arr2.length) return false;
Map<String, Integer> map1 = new HashMap<String,Integer>();
for(String str : arr1) {
if(!map.containsKey(str)) {
map.put(str, 1);
} else {
map.put(str, map.get(str) + 1); // add to count inthe map
}
}
for(String str : arr1) {
if(!map.containsKey(str)) {
return false; // we have an element in arr2 not in arr1 - leave now
} else {
map.put(str, map.get(str) - 1); // remove to count inthe map
}
}
for(Integer count : map.values()) {
if(count.intValue() != 0) return false;
}
return true;
}
Set::equalsДля этого вам не нужны внешние библиотеки. Set<> уже имеет метод equals, который делает независимое от заказа сравнение.
public static <T> boolean areArraysEquivalent(T[] ary1, T[] ary2) {
if (ary1 == null) {
return ary2 == null;
}
if (ary2 == null) {
return false;
}
List<T> list1 = Arrays.asList(ary1);
List<T> list2 = Arrays.asList(ary2);
return areListsEquivalent(list1, list2);
}
public static <T> boolean areListsEquivalent(List<T> list1, List<T> list2) {
if (list1 == null) {
return list2 == null;
}
if (list2 == null) {
return false;
}
Set<T> set1 = new HashSet<>(list1);
Set<T> set2 = new HashSet<>(list2);
return set1.equals(set2);
}
Я предполагаю, что это для школы.
Возможные стратегии:
Сначала я бы отсортировал 2 массива, а затем сравнил строки за строкой...
public boolean areArraysEqual (String[] array1,String[] array2){
if (s1.length != s2.length){
return false;
}
java.util.Arrays.sort(s1);
java.util.Arrays.sort(s2);
for (int i=0;i<s1.length;i++){
if (! s1[i].equals(s2[i])){
return false;
}
}
return true;
}
Если часто приходится сравнивать массивы друг с другом, не изменяя их содержимое, может оказаться полезным определить тип, который инкапсулирует неизменяемый массив, его отсортированную версию, число long, которое гарантировано уникальным и по крайней мере, в основном коррелирует с возрастом объекта и ссылкой на исходный нуль на другой более старый объект, который, как известно, соответствует. Также может быть полезно кэшировать хеш-значение, которое объединяет хеш-значения всех элементов массива.
Используя такой подход, сортировка будет требоваться при первом сравнении объектов с чем-либо (что-либо), но не после этого. Кроме того, если объекты X и Y оба найдены равными Z, то сравнение между X и Y может сообщать о них как о равном без фактического изучения содержимого массива (если Z старше X и Y, то оба будут сообщать себя как равные к одному и тому же более старому объекту, если X является самым младшим, а Y - самым старым, X будет знать его равным Z, а Z будет знать его равным Y. Когда X следующий по сравнению с чем-то, он узнает, что самая старая вещь, которую он знал быть равным Y, поэтому он, конечно, будет равен Y.
Такой подход обеспечит преимущества производительности сравнений по сравнению с интернированием, но без необходимости использования интернированного словаря.
Для небольших массивов я использовал бы Arrays.sort и Arrays.equals, как предложили другие. Для больших массивов вы можете использовать следующее решение, которое имеет лучшую временную сложность - O(n), а не O(n log n).
public static boolean haveSameElements(Object[] arr1, Object[] arr2) {
return arr1.length == arr2.length && counts(arr1).equals(counts(arr2));
}
// Map.merge and method references require Java 8
private static <T> Map<T, Integer> counts(T[] arr) {
Map<T, Integer> map = new HashMap<>();
for (T t : arr)
map.merge(t, 1, Integer::sum);
return map;
}