Найти уникальные предметы из двух массивов

Мне было интересно, что могло бы стать лучшим решением, которое могло бы создать меньшую сложность, чем O(n^2) при печати уникальных предметов из двух массивов. Есть идеи?Найти уникальные предметы из двух массивов

int[] a = {1,2,4,5,8}; 
    int[] b = {3,2,5,7,8}; 

    ArrayList unMatch = new ArrayList() ; 
    for(int i=0; i<a.length; i++){ 
     boolean contains = false; 
     innerloop: 
      for(int k =0; k<b.length; k++){ 
       if(a[i]==b[k]){ 
        contains = true; 
        break innerloop; 
       } 
      } 
     if(!contains){ 
      unMatch.add(a[i]); 
     } 

    } 
    for(int i=0; i<b.length; i++){ 
     boolean contains = false; 
     innerloop: 
     for(int k =0; k<a.length; k++){ 
      if(b[i]==a[k]){ 
       contains = true; 
       break innerloop; 
      } 
     } 
     if(!contains){ 
      unMatch.add(b[i]); 
     } 
    }

Выход: [1,4,3,7]

источник

2016-02-15 Atif Imran

Вы можете сделать это в 'O (n log n)', сначала отсортировав массивы. –

Конечно, это первое. Спасибо –

И самое быстрое, что вы могли бы сделать это, было бы * 'O (n + m)' *, так как в любом случае вам нужно перебирать элементы из обоих массивов. – Idos

Я думаю, что такого рода решение будет лучше, если вы можете использовать другие структуры данных:

Сначала мы пополнит HashMap<Integer, Integer> с деталями и их частоты:

public static Set<Entry<Integer, Integer>> fillMap(int[] a, int[] b) { 
    HashMap<Integer, Integer> entries = new HashMap<>();  
    for (Integer i : a) 
     entries.put(i, entries.get(i) == null ? 1 : entries.get(i) + 1); 

    for (Integer i : b) 
     entries.put(i, entries.get(i) == null ? 1 : entries.get(i) + 1); 

    return entries.entrySet(); 
}

и затем распечатать й е уникальные предметы (те, со значением = 1):

for (Entry<Integer, Integer> entry: fillMap(a, b)) 
    if (entry.getValue() == 1) 
     System.out.println("This value is unique: " + entry.getKey());

Если я не ошибаюсь, это должно работать в O(n+m) (или просто O(n) если массивы одинаковой длины всегда).

источник

2016-02-15 19:35:41 Idos

Я чувствую, что это O (n + m) –

Это то, что я написал ... В любом случае это линейно, и если размеры массива одинаковы, то он * O (n + n) = O (2n) = О (п) '* – Idos

преобразования массива в список массива

List<Integer> c = Array.asList(a); 
List<Integer> d = Array.asList<b>; 
c.removeAll(d); 
c.addAll(d); 
c.froEach(System.out::println);

Я сделал это в Java, используя лямбды это только O (п)

Надежда этот код отвечает на ваш вопрос

источник

2016-02-15 19:40:49 SmashCode

Использование набора может уменьшить ваши сложность. Наборы не позволяют дублировать. Наборы могут быть:

HashSet - HashSet реализуется с использованием хэш-таблицы. Элементы не упорядочены. Методы add, remove и contains имеют постоянную временную сложность O (1).
LinkedHashSet - использует деревья (RB-деревья). Элементы не упорядочены. Сложность для тех же методов - O (log n)
TreeSet - использует хеш-таблицу со связанным списком, проходящим через нее. Элементы упорядочены. Сложность времени тех же методов - O (1).

E.g.

HashSet<Integer> set = new HashSet<>(); 
    for(int n : a) { 
     set.add(n); 
    } 
    for (int n : b) { 
     set.add(n); 
    }

Таким образом, он обеспечивает линейный порядок здесь - O (n + m).

источник

2016-02-19 10:16:05 karzler007

Найти уникальные предметы из двух массивов

ответ

Смежные вопросы