Удалите строки из ArrayList # 1, которые появляются в другом ArrayList # 2 и не являются уникальными в ArrayList # 1

Question

Существует два массива:

ArrayList<Integer[]> arr1 = new ArrayList<Integer[]>();
ArrayList<Integer[]> arr2 = new ArrayList<Integer[]>();
arr1.add(new Integer[]{1,2,3});
arr1.add(new Integer[]{1,2,2});
arr1.add(new Integer[]{1,2,3});
arr1.add(new Integer[]{1,1,1});
arr1.add(new Integer[]{1,1,1});

arr2.add(new Integer[]{1,2,3});
arr2.add(new Integer[]{1,2,2});

Как удалить строки из arr1, которые появляются в arr2 и не являются уникальными в arr1? Например. в этом примере мне нужно будет удалить только {1,2,3}, потому что он появляется более чем один раз в arr1. Единственное решение, которое приходит мне в голову, - это использовать 4 цикла FOR, но это, похоже, очень неэффективное решение.

Изменить # 1 Результирующий arr1: {1,2,3},{1,2,2},{1,1,1},{1,1,1}

Answer 1

В случае, если вы можете использовать List вместо массива, вы можете сделать следующее:

List<List<Integer>> arr1 = new ArrayList<List<Integer>>();        
List<List<Integer>> arr2 = new ArrayList<List<Integer>>();

arr1.add(Arrays.asList(new Integer[]{1, 2, 3}));
arr1.add(Arrays.asList(new Integer[]{1, 2, 3}));
arr1.add(Arrays.asList(new Integer[]{1, 2, 2}));
arr1.add(Arrays.asList(new Integer[]{1, 2, 3}));
arr1.add(Arrays.asList(new Integer[]{1, 1, 1}));
arr1.add(Arrays.asList(new Integer[]{1, 1, 1}));

arr2.add(Arrays.asList(new Integer[]{1, 2, 3}));
arr2.add(Arrays.asList(new Integer[]{1, 2, 2}));

System.out.println(arr1);
System.out.println(arr2);

Set<List<Integer>> set1 = new HashSet<List<Integer>>();        
Iterator<List<Integer>> it = arr1.iterator(); 

while(it.hasNext()) {
    List<Integer> curr = it.next();
    if(!set1.add(curr) && arr2.contains(curr)) {
        it.remove();
    }
}

System.out.println(arr1);

Выход:

[[1, 2, 3], [1, 2, 3], [1, 2, 2], [1, 2, 3], [1, 1, 1], [1, 1, 1]]
[[1, 2, 3], [1, 2, 2]]
[[1, 2, 3], [1, 2, 2], [1, 1, 1], [1, 1, 1]]

Answer 2

Сортировка списка 1. Перебрать список 1, начиная с [1].Если есть дубликат (a[i] == a[i-1]), найдите этот массив в списке 2. Если он есть, удалите a[i].

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

Это приведет к удалению всех дубликатов из списка 1.

Answer 3

Использование списка будет примерно таким:

Loop through 2 
For every element A, loop through 1 and delete element B if it matches A.

Если вы просто оставите удаленный элемент как ноль и очистите только пустое место, оставленное удалением в конце, вместо того, чтобы пытаться все время сдвигать элементы, это уменьшит величину смещения (O (n) операции) и улучшить общее время с O(n^2*m^2) до O(n*m).

Если вы можете использовать sorted List1, вы можете искать и удалять в O (logn), общая сложность будет тогда mlogn

Если вы можете использовать HashMap, что позволит вам искать и удалять в O (1), вы можете еще больше уменьшить сложность времени до O(m), тогда вы можете использовать один цикл для просмотра списка 2 и удалить из множества 1 все тот же элемент.

Loop through List 1
     Add element to HashMap:Element -> Count (the count is here to preserve duplicates)
     If already exist in HashMap, Count++
Loop through List 2 
     For every element A, set B.get(A) = 0
Iterate through the HashMap
     For every entry, add the entry to the List *Count* times (rebuild list)

Если вы делаете это по-настоящему, существуют вспомогательные методы на каждом этапе, используйте их.

Answer 4

Используйте Set s, чтобы удалить неуникальных.Затем вы можете использовать removeAll и retainAll.Используйте класс-оболочку для Integer[] (или int[]), который может использовать Arrays.equals.

public class IntArray implements Comparable<IntArray> {
    Integer[] items;

    public IntArray() {
        this.items = new Integer[0];
    }

    public IntArray(int... items) {
        this.items = items;
    }
    ...
}