Поиск общих элементов в двух массивах разного размера

Question

У меня проблема с поиском общих элементов в двух массивах, и они имеют разный размер.

Take, Array A1 размера n и Array A2 размера m и m != n

До сих пор я пытался перебирать списки один за другим и копировать элементы в другой список.Если элемент уже содержит, отметьте его, но я знаю, что это не хорошее решение.

Answer 1

Сортировка массивов.Затем итерируйте их с помощью двух указателей, всегда перемещая один указатель на меньшее значение.Когда они указывают на равные значения, у вас есть общее значение.Это будет O (n + m), где n и m - размеры двух списков.Это похоже на слияние в сортировка слиянием , но когда вы производите вывод только тогда, когда указанные значения равны.

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

выводит

Common values: 1, 4

Еслиэлементы не сравнимы, выбросьте элементы из одного списка в хэш-карту и проверьте элементы во втором списке по хэш-карте.

Answer 2

Если вы хотите повысить его эффективность, я бы преобразовал меньший массив в хэш-набор, а затем перебрал массив большего размера и проверил, содержался ли текущий элемент в хэш-наборе. Хэш-функция эффективна по сравнению с сортировочными массивами. Сортировка массивов стоит дорого.

Вот мой пример кода

import java.util.*;
public class CountTest {     
    public static void main(String... args) {        
        Integer[] array1 = {9, 4, 6, 2, 10, 10};
        Integer[] array2 = {14, 3, 6, 9, 10, 15, 17, 9};                    
        Set hashSet = new HashSet(Arrays.asList(array1)); 
        Set commonElements = new HashSet();        
        for (int i = 0; i < array2.length; i++) {
            if (hashSet.contains(array2[i])) {
                commonElements.add(array2[i]);
            }
        }
        System.out.println("Common elements " + commonElements);
    }    
}

Выход:

Общие элементы [6, 9, 10]

Answer 3

В APL:

∪A1∩A2

пример:

      A1←9, 4, 6, 2, 10, 10
      A1
9 4 6 2 10 10

      A2←14, 3, 6, 9, 10, 15, 17, 9
      A2
14 3 6 9 10 15 17 9

      A1∩A2
9 6 10 10
      ∪A1∩A2
9 6 10 

Answer 4

Я решаю проблему, используя Set пересечение.Это очень элегантно.Несмотря на то, что я не анализировал временную сложность, она, вероятно, находится в разумных пределах.

public Set FindCommonElements(Integer[] first, Integer[] second)
{

    Set<Integer> set1=new HashSet<Integer>(Arrays.asList(first));
    Set<Integer> set2=new HashSet<Integer>(Arrays.asList(second));

    // finds intersecting elements in two sets
    set1.retainAll(set2);

    return set1;

}

Answer 5

class SortedArr

    def findCommon(a,b)

      j =0
      i =0
      l1=a.length
      l2=b.length

      if(l1 > l2)
            len=l1
      else
            len=l2
      end


     while i < len
          if a[i].to_i > b[j].to_i
              j +=1
          elsif a[i].to_i < b[j].to_i
              i +=1
          else   
              puts a[i] # OR store it in other ds
              i +=1
              j +=1
          end
     end
  end
end

 t = SortedArr.new
 t.findCommon([1,2,3,4,6,9,11,15],[1,2,3,4,5,12,15])

Answer 6

В Python вы написали бы set(A1).intersection(A2). Это оптимальный O (n + m).

Хотя в вашем вопросе есть двусмысленность. Каков результат A1 = [0, 0], A2 = [0, 0, 0]? Существуют разумные интерпретации вашего вопроса, которые дают 1, 2, 3 или 6 результатов в окончательном массиве - чего требует ваша ситуация?

Answer 7

Сложность того, что я даю, - O(N*M + N).

Также обратите внимание, что это Псевдокод C И что он предоставляет различные значения.

напр. [1,1,1,2,2,4] и [1,1,1,2,2,2,5] Вернет [1,2]

Сложность N*M причина появления for петель

+ N причина проверки, если она уже существует в ArrayCommon[] (размер n в случае, если Array2[] содержит данные, которые дублируют часть Array1[]. Предполагается, что N - это размер меньшего массива (N

int Array1[m] = { Whatever };
int Array2[n] = { Whatever };
int ArrayCommon[n] = { };

void AddToCommon(int data)
{
    //How many commons we got so far?
    static int pos = 0; 
    bool found = false;
    for(int i = 0 ; i <= pos ; i++)
    {
        //Already found it?
        if(ArrayCommon[i] == data)
        {
            found = true;
        }
    }
    if(!found)
    {
        //Add it
        ArrayCommon[pos] = data;
        pos++;
    }
}

for(int i = 0 ; i < m ; i++)
{
    for(int j = 0 ; j < n ; j++)
    {
        //Found a Common Element!
        if(Array1[i] == Array2[j])
            AddToCommon(Array1[i]);
    }
}

Answer 8

Попробуйте heapifying оба массива, а затем объединение, чтобы найти пересечение.

Пример Java:

public static <E extends Comparable<E>>List<E> intersection(Collection<E> c1,
                                                            Collection<E> c2) {
    List<E> result = new ArrayList<E>();
    PriorityQueue<E> q1 = new PriorityQueue<E>(c1),
                     q2 = new PriorityQueue<E>(c2);
    while (! (q1.isEmpty() || q2.isEmpty())) {
        E e1 = q1.peek(), e2 = q2.peek();
        int c = e1.compareTo(e2);
        if (c == 0) result.add(e1);
        if (c <= 0) q1.remove();
        if (c >= 0) q2.remove();
    }
    return result;
}

См. этот вопрос длябольше примеров слияния.

Answer 9

Похоже на вложенные циклы:

commons = empty
for each element a1 in A1
   for each element a2 in A2
      if a1 == a2
         commons.add(a1)

Не имеет значения, если массивы имеют одинаковый размер.

В зависимости от используемого языка и структуры операции множеств могут оказаться полезными.