Пересечение двух отсортированных массивов
Даны два отсортированных массива: A а также B, Размер массива A является La и размер массива B является Lb, Как найти пересечение A а также B?
Если La намного больше чем Lb, тогда будет ли какая-то разница для алгоритма поиска пересечения?
9 ответов
Использование set_intersection как здесь Обычная реализация будет работать аналогично части слияния алгоритма сортировки слиянием.
Так как это выглядит как HW... Я дам вам алгоритм:
Let arr1,arr2 be the two sorted arrays of length La and Lb.
Let i be index into the array arr1.
Let j be index into the array arr2.
Initialize i and j to 0.
while(i < La and j < Lb) do
if(arr1[i] == arr2[j]) { // found a common element.
print arr[i] // print it.
increment i // move on.
increment j
}
else if(arr1[i] > arr2[j])
increment j // don't change i, move j.
else
increment i // don't change j, move i.
end while
Некоторое время я боролся с той же проблемой, так что я пришел с:
Линейное соответствие, которое в худшем случае даст O(m+n). Вы в основном сохраняете два указателя (A и B), каждый из которых указывает на начало каждого массива. Затем перемещайте указатель, который указывает на меньшее значение, пока вы не достигнете конца одного из массивов, который бы указывал на отсутствие пересечения. Если в какой-то момент у вас есть *A == *B - здесь идет ваше пересечение.
Двоичное сопоставление. Что дает ~ O(n*log(m)) в худшем случае. Вы в основном выбираете меньший массив и выполняете бинарный поиск в большем массиве всех элементов меньшего массива. Если вы хотите быть более навороченным, вы можете даже использовать последнюю позицию, где бинарный поиск не удался, и использовать ее в качестве отправной точки для следующего бинарного поиска. Таким образом, вы незначительно улучшаете худший случай, но для некоторых наборов он может творить чудеса:)
Двойное двоичное сопоставление. Это вариант обычного двоичного соответствия. В основном вы получаете элемент из середины меньшего массива и выполняете бинарный поиск в большем массиве. Если вы ничего не нашли, вы разрезаете меньший массив пополам (и да, вы можете отбросить элемент, который вы уже использовали) и разрезаете больший массив пополам (используйте точку сбоя двоичного поиска). А затем повторите для каждой пары. Результаты лучше, чем O (n * log (m)), но мне лень вычислять, что они из себя представляют.
Это два самых основных из них. У обоих есть свои достоинства. Линейный немного проще в реализации. Двоичный вариант, возможно, быстрее (хотя существует множество случаев, когда линейное сопоставление превосходит двоичное).
Если кто-нибудь знает что-то лучше, я бы хотел это услышать. Сравнение массивов - это то, чем я занимаюсь в наши дни.
PS Не цитируйте меня по терминам "линейное соответствие" и "бинарное соответствие", так как я их сам придумал, и, возможно, для этого уже есть причудливое название.
Это на Java, но делает то, что вы хотите. Он реализует вариант 3, упомянутый в ответе Назара ("двойной" двоичный поиск), и должен быть самым быстрым решением. Я почти уверен, что это лучше, чем любой "скачущий" подход. Скачок просто тратит время на то, чтобы начать с небольших шагов, в то время как мы сразу переходим к бинарному поиску сверху вниз.
Не сразу очевидно, какой класс сложности здесь применяется. Мы выполняем двоичный поиск в более длинном массиве, но никогда не смотрим на один и тот же элемент дважды, поэтому мы определенно находимся в пределах O(m+n).
Этот код был тщательно протестирован со случайными данными.
import java.util.Arrays;
// main function. may return null when result is empty
static int[] intersectSortedIntArrays(int[] a, int[] b) {
return intersectSortedIntArrays(a, b, null);
}
// no (intermediate) waste version: reuse buffer
static int[] intersectSortedIntArrays(int[] a, int[] b, IntBuffer buf) {
int i = 0, j = 0, la = lIntArray(a), lb = lIntArray(b);
// swap if a is longer than b
if (la > lb) {
int[] temp = a; a = b; b = temp;
int temp2 = la; la = lb; lb = temp2;
}
// special case zero elements
if (la == 0) return null;
// special case one element
if (la == 1)
return Arrays.binarySearch(b, a[0]) >= 0 ? a : null;
if (buf == null) buf = new IntBuffer(); else buf.reset();
intersectSortedIntArrays_recurse(a, b, buf, 0, la, 0, lb);
return buf.toArray();
}
static void intersectSortedIntArrays_recurse(int[] a, int[] b, IntBuffer buf, int aFrom, int aTo, int bFrom, int bTo) {
if (aFrom >= aTo || bFrom >= bTo) return; // nothing to do
// start in the middle of a, search this element in b
int i = (aFrom+aTo)/2;
int x = a[i];
int j = Arrays.binarySearch(b, bFrom, bTo, x);
if (j >= 0) {
// element found
intersectSortedIntArrays_recurse(a, b, buf, aFrom, i, bFrom, j);
buf.add(x);
intersectSortedIntArrays_recurse(a, b, buf, i+1, aTo, j+1, bTo);
} else {
j = -j-1;
intersectSortedIntArrays_recurse(a, b, buf, aFrom, i, bFrom, j);
intersectSortedIntArrays_recurse(a, b, buf, i+1, aTo, j, bTo);
}
}
static int lIntArray(int[] a) {
return a == null ? 0 : a.length;
}
static class IntBuffer {
int[] data;
int size;
IntBuffer() {}
IntBuffer(int size) { if (size != 0) data = new int[size]; }
void add(int i) {
if (size >= lIntArray(data))
data = resizeIntArray(data, Math.max(1, lIntArray(data)*2));
data[size++] = i;
}
int[] toArray() {
return size == 0 ? null : resizeIntArray(data, size);
}
void reset() { size = 0; }
}
static int[] resizeIntArray(int[] a, int n) {
if (n == lIntArray(a)) return a;
int[] b = new int[n];
arraycopy(a, 0, b, 0, Math.min(lIntArray(a), n));
return b;
}
static void arraycopy(Object src, int srcPos, Object dest, int destPos, int n) {
if (n != 0)
System.arraycopy(src, srcPos, dest, destPos, n);
}
void Intersect()
{
int la, lb;
la = 5;
lb = 100;
int A[5];
int i, j, k;
i = j = k = 0;
for (; i < 5; ++i)
A[i] = i + 1;
int B[100];
for (; j < 100; ++j)
B[j] = j + 2;
int newSize = la < lb ? la : lb;
int* C = new int[newSize];
i = j = 0;
for (; k < lb && i < la && j < lb; ++k)
{
if (A[i] < B[j])
i++;
else if (A[i] > B[j])
j++;
else
{
C[k] = A[i];
i++;
j++;
}
}
for (k = 0; k < newSize; ++k)
cout << C[k] << NEWLINE;
}
Вот ответ, который я тестировал, чтобы сопоставить два массива, которые оба отсортированы, но могут иметь повторяющиеся ключи и значения в качестве записей. Т.е. оба списка отсортированы по ключу 'timestamp'. Затем .equals обнаруживает соответствие. Этот находит пересечение a и b, где пересечение дубликатов потребляет их. Т.е. каждый элемент a, который соответствует элементу b, использует эту запись. Извините за специфику здесь из конкретного проекта, но, возможно, это полезно.
Я, наконец, сделал решение ниже после того, как много пропустил с HashSet (не обрабатывает дубликаты), Guava MultiSet (отлично, но если вы посмотрите на это, у него много служебных проверок).
/**
* Finds the intersection of events in a that are in b. Assumes packets are
* non-monotonic in timestamp ordering.
*
*
* @param a ArrayList<BasicEvent> of a
* @param b likewise
* @return ArrayList of intersection
*/
private ArrayList<BasicEvent> countIntersect(ArrayList<BasicEvent> a, ArrayList<BasicEvent> b) {
ArrayList<BasicEvent> intersect = new ArrayList(a.size() > b.size() ? a.size() : b.size());
int count = 0;
if (a.isEmpty() || b.isEmpty()) {
return new ArrayList();
}
// TODO test case
// a = new ArrayList();
// b = new ArrayList();
// a.add(new BasicEvent(4, (short) 0, (short) 0)); // first arg is the timestamp
// a.add(new BasicEvent(4, (short) 0, (short) 0));
// a.add(new BasicEvent(4, (short) 1, (short) 0));
// a.add(new BasicEvent(4, (short) 2, (short) 0));
//// a.add(new BasicEvent(2, (short) 0, (short) 0));
//// a.add(new BasicEvent(10, (short) 0, (short) 0));
//
// b.add(new BasicEvent(2, (short) 0, (short) 0));
// b.add(new BasicEvent(2, (short) 0, (short) 0));
// b.add(new BasicEvent(4, (short) 0, (short) 0));
// b.add(new BasicEvent(4, (short) 0, (short) 0));
// b.add(new BasicEvent(4, (short) 1, (short) 0));
// b.add(new BasicEvent(10, (short) 0, (short) 0));
int i = 0, j = 0;
int na = a.size(), nb = b.size();
while (i < na && j < nb) {
if (a.get(i).timestamp < b.get(j).timestamp) {
i++;
} else if (b.get(j).timestamp < a.get(i).timestamp) {
j++;
} else {
// If timestamps equal, it might be identical events or maybe not
// and there might be several events with identical timestamps.
// We MUST match all a with all b.
// We don't want to increment both pointers or we can miss matches.
// We do an inner double loop for exhaustive matching as long as the timestamps
// are identical.
int i1 = i, j1 = j;
while (i1 < na && j1 < nb && a.get(i1).timestamp == b.get(j1).timestamp) {
boolean match = false;
while (j1 < nb && i1 < na && a.get(i1).timestamp == b.get(j1).timestamp) {
if (a.get(i1).equals(b.get(j1))) {
count++;
intersect.add(b.get(j1)); // TODO debug
// we have a match, so use up the a element
i1++;
match = true;
}
j1++;
}
if (!match) {
i1++; //
}
j1 = j; // reset j to start of matching timestamp region
}
i = i1; // when done, timestamps are different or we reached end of either or both arrays
j = j1;
}
}
// System.out.println("%%%%%%%%%%%%%%");
// printarr(a, "a");
// printarr(b, "b");
// printarr(intersect, "intsct");
return intersect;
}
// TODO test case
void printarr(ArrayList<BasicEvent> a, String n) {
final int MAX = 30;
if (a.size() > MAX) {
System.out.printf("--------\n%s[%d]>%d\n", n, a.size(), MAX);
return;
}
System.out.printf("%s[%d] --------\n", n, a.size());
for (int i = 0; i < a.size(); i++) {
BasicEvent e = a.get(i);
System.out.printf("%s[%d]=[%d %d %d %d]\n", n, i, e.timestamp, e.x, e.y, (e instanceof PolarityEvent) ? ((PolarityEvent) e).getPolaritySignum() : 0);
}
}
Очень просто с питоном
Пример: A = [1,2,3,5,7,9,90] B = [2,4,10,90]
Здесь мы идем три строки кода
for i in A:
if(i in B):
print(i)
Выход:2, 90
Давайте рассмотрим два отсортированных массива:
int[] array1 = {1,2,3,4,5,6,7,8};
int[] array2 = {2,4,8};
int i=0, j=0; //taken two pointers
Цикл while будет работать, пока оба указателя не дойдут до соответствующей длины.
while(i<array1.length || j<array2.length){
if(array1[i] > array2[j]) //if first array element is bigger then increment 2nd pointer
j++;
else if(array1[i] < array2[j]) // same checking for second array element
i++;
else { //if both are equal then print them and increment both pointers
System.out.print(a1[i]+ " ");
if(i==a1.length-1 ||j==a2.length-1) //one additional check for ArrayOutOfBoundsException
break;
else{
i++;
j++;
}
}
}
Выход будет: -
2 4 8
//intersection of two arrays
#include<iostream>
using namespace std;
int main() {
int i=0,j=0,m,n;
int arr1[i],arr2[j];
cout<<"Enter the number of elements in array 1: ";
cin>> m;
cout<<"Enter the number of elements in array 2: ";
cin>>n;
for (i=0;i<m;i++){
cin>> arr1[i];
}
for(j=0;j<n;j++){
cin>> arr2[j];
}
for(j=0;j<n;j++){
for(i=0;i<m;i++) {
if (arr1[i] == arr2[j]){
cout<< arr1[i];
cout << ' ';
break;
}
}
}
return 0;
}