Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Слияние, пересечение и разности массивов на JavaScript

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


Слияние массивов на JavaScript


Постановка задачи. Пусть заданы два числовых массива [math]A[/math] и [math]B[/math], упорядоченных по возрастанию. Требуется написать функцию, возвращающую третий массив [math]C[/math], также упорядоченного по возрастанию и содержащего элементы как массива [math]A[/math], так и массива [math]C[/math].


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


Пример реализации алгоритма слияния на 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


Пересечение двух массивов [math]A[/math] и [math]B[/math] — это массив только с теми элементами [math]A[/math] и [math]B[/math], которые одновременно принадлежат обоим массивам, без дублей.


Сложность алгоритма [math]O(m\cdot n)[/math], где [math]m[/math] и [math]n[/math] — длины входных массивов [math]A[/math] и [math]B[/math] соответственно.


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) );
}

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


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


Разность двух массивов [math]A[/math] и [math]B[/math] — это массив с элементами [math]A[/math], несовпадающими с элементами [math]B[/math], без дублей.


Сложность алгоритма [math]O(m\cdot n)[/math], где [math]m[/math] и [math]n[/math] — длины входных массивов [math]A[/math] и [math]B[/math] соответственно.


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].

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


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, без повторов.

Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved