Алгоритмы слияния, пересечения, разности и объединения массивов на JavaScript

Постановка задачи. Пусть заданы два числовых массива A и B, упорядоченных по возрастанию. Требуется написать функцию, возвращающую третий массив C, также упорядоченного по возрастанию и содержащего элементы как массива A, так и массива C. Опишем алгоритм решения данной задачи, который называется алгоритмом слияния двух упорядоченных массивов. Чтобы объединить два упорядоченных массива A и B в упорядоченный массив C, используется цикл for, который помещает элемент в массив C на каждой итерации. Если A исчерпан, элемент берется из B; если исчерпан B, то элемент берется из A; если же элементы остаются и в том и в другом массиве, наименьший из оставшихся элементов в A и B переходит в C. Пример реализации алгоритма слияния на JavaScript.

function merge(A,B)                     // A и B - упорядоченные массивы.
{
    var N = A.length, M = B.length, C = [];

    for (var i = 0, j = 0, k = 0; k < N+M; k++)
     { if (i == N){ C[k] = B[j++]; continue; }
       if (j == M){ C[k] = A[i++]; continue; }
       C[k] = (A[ i ] < B[j]) ? A[i++] : B[j++];
     }
                                              // На выходе упорядоченный массив C,
    return C;                                 // состоящий из элементов A и B.
}

Множественное слияние массивов на JavaScript. Ниже представлена рекурсивная функция для множественного слияния, которая позволяет сливать более двух массивов.

function MultiMerge(k,A)   // При вызовах всегда пологать k=0. А - это двумерный (!) массив,
{                          //  элементы которого A[ i ] - упорядоченные массивы, которые нужно слить.
    var n = A.length;
    if (k == n-2)
       return merge( A[n-2], A[n-1] );   // Функцию merge см. выше.
    else
       return merge( A[k], MultiMerge(k+1,A) );  // На выходе упорядоченный одномерный массив,
                                                 //  состоящий из элементов A[ i ] входного 2d-массива A.
}
 // Пример вызова этой функции:  MultiMerge( 0,[[3,4],[-9,-2,0,1],[5,6,7],[-8,-7]] ).
 //          На выходе получим:  [-9,-8,-7,-2,0,1,3,4,5,6,7].

Пересечение двух массивов \( A \) и \( B \) — это массив только с теми элементами \( A \) и \( B \), которые одновременно принадлежат обоим массивам, без дублей. Сложность алгоритма \( O(m\cdot n) \), где m и n — длины входных массивов \( A \) и \( B \)соответственно.

function IntersecArrays(A,B)
{
    var m = A.length, n = B.length, c = 0, C = [];
    for (var i = 0; i < m; i++)
     { var j = 0, k = 0;
       while (B[j] !== A[ i ] && j < n) j++;
       while (C[k] !== A[ i ] && k < c) k++;
       if (j != n && k == c) C[c++] = A[ i ];
     }
   return C;
}

Множественное пересечение массивов

function MultiIntersecArrays(k,A)  // При вызовах всегда полагать k=0. А - это двумерный (!)
{                                   //  массив, элементы которого A[ i ] - также массивы,
    var n = A.length;               //  пересечение которых нужно найти.
    if (k == n-2)
       return IntersecArrays( A[n-2], A[n-1] );   // Функцию IntersecArrays см. выше.
    else
       return IntersecArrays( A[k], MultiIntersecArrays(k+1,A) );
}

Пересечение упорядоченных массивов. Если же масссивы \( A \) и \( B \) упорядочены, то несложно составить алгоритм, работающий за \( O(m+n) \).

function IntersecSortArr(A,B)         // A и B - упорядоченные массивы.
{
    var M = A.length, N = B.length, C = [],
        m = 1, n = 1, k = 0, a = 0, b = 0;

    for (var i = 1, t = A[0]; i < M; i++)  // Сдвигаем в начало уникальные элементы
     { if (A[ i ] !== t)                   // Первые m-элементов будут уникальными
        { A[m++] = A[ i ]; t = A[ i ]; }
     }

    for (var i = 1, t = B[0]; i < N; i++)  // Аналогично предыдущему
     { if (B[ i ] !== t)
        { B[n++] = B[ i ]; t = B[ i ]; }
     }

    while (a < m && b < n)                // Заносим в C только те элементы A и B,
     { if (A[ a ] < B[ b ]) ++a;          //  которые есть в них обоих
       else if (A[ a ] > B[ b ]) ++b;
       else С[k++] = A[a++];
     }

    return C;   // На выходе массив C, состоящий из элементов массивов A и B,
}               //  которые есть в обоих массивах, без повторов.

Множественное пересечение упорядоченных массивов

function MultiIntersecSortArr(k,A)  // При вызовах всегда полагать k=0. А - это двумерный (!)
{                                   //  массив, элементы которого A[ i ] - упорядоченные массивы,
    var n = A.length;               //  пересечение которых нужно найти.
    if (k == n-2)
       return IntersecSortArr( A[n-2], A[n-1] );   // Функцию IntersecSortArr() см. выше.
    else
       return IntersecSortArr( A[k], MultiIntersecSortArr(k+1,A) );
}

Разность двух массивов A и B — это массив с элементами A, несовпадающими с элементами B, без дублей. Сложность алгоритма \( O(m\cdot n) \), где m и n — длины входных массивов A и B соответственно.

function DiffArrays(A,B)
{
    var M = A.length, N = B.length, c = 0, C = [];
    for (var i = 0; i < M; i++)
     { var j = 0, k = 0;
       while (B[j] !== A[ i ] && j < N) j++;
       while (C[k] !== A[ i ] && k < c) k++;
       if (j == N && k == c) C[c++] = A[ i ];
     }
   return C;
}

Множественная разность массив

function MultiDiffArrays(k,A)   // При вызовах всегда полагать k=0. А - это двумерный (!)
{                                //  массив, элементы которого A[ i ] - упорядоченные массивы,
    var n = A.length;            //  разность которых нужно найти.
    if (k == n-2)
       return DiffArrays( A[n-2], A[n-1] );      // Функцию DiffArrays см. выше.
    else
       return DiffArrays( A[k], MultiDiffArrays(k+1,A) );
}                 // На выходе массив A[0],в котором останутся только те элементы (без дублей),
                  //  которые не совпадают с элементами массивов A[1],…,A[n-1].

Разность упорядоченных массивов. Если же масссивы A и B упорядочены, то несложно составить алгоритм, работающий за \( O(m+n) \).

function DiffSortArr(A,B)     // A и B - упорядоченные массивы.
{
    var C = IntersecSortArr(A,B),    // C - массив элементов, которые есть
        M = A.length,                //   и в массиве A и в массиве B.
        N = C.length;                // Функцию IntersecSortArr() см. выше.

    for (var i=0, k=0, a=0, c=0; i<M+N; i++)  // Оставляем в A только те элементы,
     { if (A[ a ] === C[ c ]) { ++a; ++c; }   //   которых нет в пересечении A и B,
       else  { A[k] = A[ i ]; k++; a++; }     //   то есть в массиве C.
     }                                        // Математически: удаление из множества
    A.length = k;                             //  его подмножества.

                  // На выходе массив A, в котором останутся только те
    return A;     //  элементы (без дублей), которых нет в массиве B.
}

Множественная разность упорядоченных массивов

function MultiDiffSortArr(k,A)   // При вызовах всегда полагать k=0. А - это двумерный (!)
{                                //  массив, элементы которого A[ i ] - упорядоченные массивы,
    var n = A.length;            //  разность которых нужно найти.
    if (k == n-2)
       return DiffSortArr( A[n-2], A[n-1] );      // Функцию DiffSortArr() см. выше.
    else
       return DiffSortArr( A[k], MultiDiffSortArr(k+1,A) );
}                 // На выходе массив A[0],в котором останутся только те элементы (без дублей),
                  //  которые не совпадают с элементами массивов A[1],…,A[n-1].

Симметрическая разность массивов

function SymmDiffSortArr(A,B)     // A и B - упорядоченные массивы.
{
    var N = A.length, M = B.length;

    for (var i=1, j=1, k=A[0]; i<N; i++)       // Удаляем повторяющиеся элементы
     { if (A[ i ] !== k)                       // в сортированных массивах А и B.
        { A[j++] = A[ i ]; k = A[ i ]; }
     }
    A.length = j;

    for (var i=1, j=1, k=B[0]; i<M; i++)
     { if (B[ i ] !== k)
        { B[j++] = B[ i ]; k = B[ i ]; }
     }
    B.length = j;                              // end

    var N = A.length, M = B.length, C = [];

    for (var i=0, j=0, k=0; k<N+M; k++)        // Сливаем массивы A и B в массив С,
     { if (i==N){ C[k] = B[j++]; continue; }   //  сохраняя упорядоченность.
       if (j==M){ C[k] = A[i++]; continue; }
       C[k] = (A[ i ]<B[j]) ? A[i++] : B[j++];
     }

    var N = C.length;

    for (var i=1, j=0, t; i<N+1; i++)          // Сдвигаем в начало массива С элементы,
     { if (C[i-1] === C[ i ]) t = C[i-1];        //  которые не имеют дубли,
       if (C[i-1] !== t) C[j++] = C[i-1];      //  их будет j-штук.
     }                                         // Оставляем в C j-элементов,
    C.length = j;                              //  не имеющих дублей.

    return C;        // На выходе массив C, состоящий из элементов множеств A и B,
                     //  которых не присутствуют одновременное в обоих массивах A и B.
}                    //  без повторяющихся элементов.

Множественная симметрическая разность упорядоченных массивов

function MultiSymmDiffSortArr(k,A)   // При вызовах всегда полагать k=0. А - это двумерный (!)
{                                    //  массив, элементы которого A[ i ] - упорядоченные массивы,
    var n = A.length;                //  симметрическую разность которых нужно найти.
    if (k == n-2)
       return SymmDiffSortArr( A[n-2], A[n-1] );     // Функцию SymmDiffSortArr() см. выше.
    else
       return SymmDiffSortArr( A[k], MultiSymmDiffSortArr(k+1,A) );
}

Объединение упорядоченных массивов

function UnionSortArr(A,B)             // A и B - упорядоченные массивы.
{
    var N = A.length, M = B.length, C = [];

    for (var i=0, j=0, k=0; k<N+M; k++)        // Сливаем массивы A и B в массив С,
     { if (i==N){ C[k] = B[j++]; continue; }   //   сохраняя упорядоченность.
       if (j==M){ C[k] = A[i++]; continue; }
       C[k] = (A[ i ]<B[j]) ? A[i++] : B[j++];
     }

    for (var i=1, j=C[0], k=1; i<N+M; i++)     // Удаляем дубли в упорядоченном
     { if (C[ i ] !== j)                       //  массиве С.
        { C[k++] = C[ i ]; j = C[ i ]; }
     }
    C.length = k;
                                // На выходе массив C, состоящий из элементов
    return C;                   //  массивов A и B, без повторов.
}

Множественное объединение упорядоченных массивов. Ниже представлена рекурсивная функция для множественного объединение упорядоченных массивов, которая позволяет объединять более двух массивов

function MultiUnionSortArr(k,A)  // При вызовах всегда полагать k=0. А - это двумерный (!)
{                                //  массив, элементы которого A[ i ] - упорядоченные массивы,
    var n = A.length;            //  которые нужно объединить.
    if (k == n-2)
       return UnionSortArr( A[n-2], A[n-1] );   // Функцию UnionSortArr см. выше.
    else
       return UnionSortArr( A[k], MultiUnionSortArr(k+1,A) );
                                       // На выходе одномерный массив, состоящий из элементов A[ i ]
}                                      //   входного 2d-массива A, без повторов.