Поиск общих элементов в двух массивах разного размера
У меня проблема найти общие элементы в двух массивах и разных размерах.
Take, Array A1
размера n
и Array A2
размера m
и m != n
До сих пор я пытался поочередно перебирать списки и копировать элементы в другой список. Если элемент уже содержит отметку, но я знаю, что это нехорошее решение.
Ответы
Ответ 1
Сортировка массивов. Затем проведите через них два указателя, всегда продвигая их, указывая на меньшее значение. Когда они указывают равные значения, у вас есть общее значение. Это будет O (n + m), где n и m - размеры этих двух списков. Это просто как слияние в merge sort, но там, где вы создаете вывод только тогда, когда указанные значения равны.
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
Если элементы не сопоставимы, выбросьте элементы из одного списка в хэш-карту и проверьте элементы во втором списке на хэш-карту.
Ответ 2
Если вы хотите сделать его эффективным, я бы преобразовал меньший массив в хешсет, а затем итерацию большего массива и проверку того, содержался ли текущий элемент в hashset. Хэш-функция эффективна по сравнению с сортировкой массивов. Сортировка массивов стоит дорого.
Здесь мой пример кода
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]
Ответ 3
Похож на вложенные петли:
commons = empty
for each element a1 in A1
for each element a2 in A2
if a1 == a2
commons.add(a1)
Не имеет значения вообще, если массивы имеют одинаковый размер.
В зависимости от используемого языка и используемой структуры, операции установки могут оказаться полезными.
Ответ 4
Попробуйте 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;
}
Подробнее о слиянии см. этот вопрос.
Ответ 5
Сложность того, что я даю, O(N*M + N)
.
Также обратите внимание, что это Pseudocode 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 < M).
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]);
}
}
Ответ 6
В Python вы должны написать set(A1).intersection(A2)
. Это оптимальный O (n + m).
Однако в вашем вопросе есть двусмысленность. Каков результат A1 = [0, 0], A2 = [0, 0, 0]? Там разумные интерпретации вашего вопроса, которые дают 1, 2, 3 или 6 результатов в конечном массиве - что требует ваша ситуация?
Ответ 7
Я решаю проблему, используя Set intersection. Это очень элегантно. Несмотря на то, что я не анализировал сложность времени, это, вероятно, в разумном диапазоне.
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;
}
Ответ 8
В 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
Ответ 9
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])