В данной публикации я проведу алгоритмизацию операций над массивами, а так же расскажу о самих операциях.
Содержание
- I. Пересечение массивов
- II. Разность массивов
- III. Объединение массивов
- IV. Симметрическая разность массивов
- Заключение
I. Пересечение массивов
Пересечение двух массивов A и B — это массив только с теми элементами A и B, которые одновременно принадлежат обоим массивам, без дублей.
Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.
function Intersection(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;
}
Пример:
Intersection ([1,2,3,7,9],[4,5,7,2,1,5]); //На выходе [1,2,7]
II. Разность массивов
Разность двух массивов A и B — это массив с элементами A, не совпадающими с элементами B, без дублей.
Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.
function Diff(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;
}
Пример:
Diff([1,2,3,7,9],[4,5,7,2,1,5]); //На выходе [3,9]
Diff([4,5,7,2,1,5], [1,2,3,7,9]); //На выходе [4,5]
III. Объединение массивов
Объединение двух массивов A и B — это массив с элементами A и элементы массива B, без дублей.
Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.
function Sum(A, B)
{
var M = A.length, N = B.length, count = 0, C = [];
C = A;
count = M;
var cnt = 0;
for (var i=0;i<N;i++)
{
var plus = false;
for (var j=0;j<M;j++)
if (C[j] == B[i]) {plus = true; break;}
if (plus === false) C[count++] = B[i];
}
return C;
}
Пример:
Sum([1,2,3,7,9],[4,5,7,2,1,5]); //На выходе [1,2,3,7,9,4,5]
Sum([4,5,7,2,1,5],[1,2,3,7,9]); //На выходе [4,5,7,2,1,5,3,9]
IV. Симметрическая разность массивов
Симметрическая разность двух массивов A и B — это такой массив, куда входят все те элементы первого массива, которые не входят во второй массив, а также те элементы второго массива, которые не входят в первый массив.
Сложность алгоритма O(2m*n), где m и n — длины входных массивов A и B соответственно.
По сути это вычитание массивов, сначала A из B, затем B из A.
function SymmetricDiff(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 ];
}
for (var i = 0; i < N; i++)
{
var j = 0, k = 0;
while (A[j] !== B[ i ] && j < M) j++;
while (C[k] !== B[ i ] && k < c) k++;
if (j == M && k == c) C[c++] = B[ i ];
}
return C;
}
Пример:
SymmetricDiff([1,2,3,7,9],[4,5,7,2,1,5]);//На выходе [3,9,4,5]
SymmetricDiff([1,2,3,4,5],[3,4,5,6,7]); //На выходе [1,2,6,7]
Заключение
Живой пример на примере друзей вконтакте. При вводе ссылок на страницы пользователей вконтакте сервис выдает все пересечения массивов друзей пользователей (пересечения — это общие друзья пользователей).
Автор: dooza