Постановка задачи. Пусть заданы два числовых массива и , упорядоченных по возрастанию. Требуется написать функцию, возвращающую третий массив , также упорядоченного по возрастанию и содержащего элементы как массива , так и массива .
Опишем алгоритм решения данной задачи, который называется алгоритмом слияния двух упорядоченных массивов. Чтобы объединить два упорядоченных массива и в упорядоченный массив , используется цикл for, который помещает элемент в массив на каждой итерации. Если исчерпан, элемент берется из ; если исчерпан , то элемент берется из ; если же элементы остаются и в том и в другом массиве, наименьший из оставшихся элементов в и переходит в .
Пример реализации алгоритма слияния на 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].
Пересечение массивов на JavaScript
Пересечение двух массивов и — это массив только с теми элементами и , которые одновременно принадлежат обоим массивам, без дублей.
Сложность алгоритма , где и — длины входных массивов и соответственно.
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) ); }
Пересечение упорядоченных массивов. Если же масссивы и упорядочены, то несложно составить алгоритм, работающий за .
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) ); }
Разность массивов на JavaScript
Разность двух массивов и — это массив с элементами , несовпадающими с элементами , без дублей.
Сложность алгоритма , где и — длины входных массивов и соответственно.
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].
Разность упорядоченных массивов. Если же масссивы и упорядочены, то несложно составить алгоритм, работающий за .
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].
Симметрическая разность массивов на JavaScript
Симметрическая разность массивов
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) ); }
Объединение массивов на JavaScript
Объединение упорядоченных массивов
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, без повторов.
Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.