В предыдущей статье я писал о бинарных операциях над неупорядоченными множествами. В этой статье мы рассмотрим алгоритмы с меньшей сложностью выполнения, для упорядоченных множеств.
![](https://habrastorage.org/r/w1560/files/e01/c50/801/e01c50801b8845729d4645a0f034ca6d.png)
Содержание
I. Пересечение упорядоченных множеств
II. Разность упорядоченных множеств
III. Объединение упорядоченных множеств
IV. Симметрическая разность упорядоченных множеств
Заключение
Пересечение двух упорядоченных множеств A и B — это множество только с теми элементами A и B, которые одновременно принадлежат обоим множествам, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных множеств A и B соответственно.
Сделал небольшую анимацию, чтобы показать как работает алгоритм.
![image](https://habrastorage.org/files/46b/8a2/f93/46b8a2f9302a451c949d800357abb64d.gif)
Пример реализации на javascript:
Обращение к функции:
Разность двух упорядоченных множеств A и B — это множество с элементами A, не совпадающими с элементами B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.
![](//habrastorage.org/files/c51/aaf/c52/c51aafc52aa545f6af0cf37ad60e27d5.gif)
Объединение двух упорядоченных множеств A и B — это множество с элементами A и элементы множества B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.
![](//habrastorage.org/files/f6b/260/9ad/f6b2609ad9724d8abbff5e968d9a028f.gif)
Симметрическая разность двух упорядоченных множеств A и B — это такое множество, куда входят все те элементы первого упорядоченного множества, которые не входят во второе упорядоченное множество, а также те элементы второго упорядоченного множества, которые не входят в первое упорядоченное множество. Сложность алгоритма O(2(m+n)), где m и n — длины входных упорядоченных множеств A и B соответственно.
По сути это вычитание множеств, сначала A из B, затем B из A.
Способ предложенный 0leGG.
Мне часто приходится работать с отсортированными массивами, поэтому эти алгоритмы очень сильно ускоряют процесс. Пример реализации метода intersec_sort_arr, вы можете посмотреть в моем приложении для vk.com. С помощью данного метода я нахожу общих участников сообществ работая с отсортированными массивами, в миллионы элементов, метод справляется очень быстро. До этого использовал метод описанный в моей предыдущей статье, обработка массивов была очень медленной.
![](https://habrastorage.org/files/e01/c50/801/e01c50801b8845729d4645a0f034ca6d.png)
Содержание
I. Пересечение упорядоченных множеств
II. Разность упорядоченных множеств
III. Объединение упорядоченных множеств
IV. Симметрическая разность упорядоченных множеств
Заключение
I. Пересечение упорядоченных множеств
Пересечение двух упорядоченных множеств A и B — это множество только с теми элементами A и B, которые одновременно принадлежат обоим множествам, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных множеств A и B соответственно.
Сделал небольшую анимацию, чтобы показать как работает алгоритм.
![image](https://habrastorage.org/files/46b/8a2/f93/46b8a2f9302a451c949d800357abb64d.gif)
Пример реализации на javascript:
function intersec_sort_arr(array_1,array_2)
{
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не дошли до конца массива
{
if (array_1[i] == array_2[j])
{
array_3[k] = array_1[i]; // запишем элемент в массив array_3
k++,i++,j++; // и сдвинем позицию во всех 3 массивах
} else {
if (array_1[i] < array_2[j]) {
i++; // сдвинем позицию в первом массиве
} else {
j++; // сдвинем позицию во втором массиве
}
}
}
return array_3;
}
Обращение к функции:
intersec_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на выходе [3, 8]
II. Разность упорядоченных множеств
Разность двух упорядоченных множеств A и B — это множество с элементами A, не совпадающими с элементами B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.
![](http://habrastorage.org/files/c51/aaf/c52/c51aafc52aa545f6af0cf37ad60e27d5.gif)
function diff_sort_arr(array_1,array_2)
{
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не дошли до конца массива
{
if (array_1[i] == array_2[j])
{
i++,j++;
} else {
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // сдвинем позицию в первом массиве
} else {
j++; // сдвинем позицию во втором массиве
}
}
}
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
return array_3;
}
diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на выходе [1, 2, 5]
III. Объединение упорядоченных множеств
Объединение двух упорядоченных множеств A и B — это множество с элементами A и элементы множества B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.
![](http://habrastorage.org/files/f6b/260/9ad/f6b2609ad9724d8abbff5e968d9a028f.gif)
function sum_sort_arr(array_1,array_2)
{
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не дошли до конца массива
{
if (array_1[i] == array_2[j])
{
array_3[k] = array_1[i];
k++,i++,j++;
} else {
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // сдвинем позицию в первом массиве
} else {
array_3[k] = array_2[j];
k++;
j++; // сдвинем позицию во втором массиве
}
}
}
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
while (j < m) {
array_3[k] = array_2[j];
k++, j++;
}
return array_3;
}
sum_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на выходе [1, 2, 3, 5, 6, 8, 12, 24, 47]
IV. Симметрическая разность упорядоченных множеств
Симметрическая разность двух упорядоченных множеств A и B — это такое множество, куда входят все те элементы первого упорядоченного множества, которые не входят во второе упорядоченное множество, а также те элементы второго упорядоченного множества, которые не входят в первое упорядоченное множество. Сложность алгоритма O(2(m+n)), где m и n — длины входных упорядоченных множеств A и B соответственно.
По сути это вычитание множеств, сначала A из B, затем B из A.
2 прохода
function symmetric_diff_sort_arr(array_1,array_2)
{
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не дошли до конца массива
{
if (array_1[i] == array_2[j])
{
i++,j++;
} else {
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // сдвинем позицию в первом массиве
} else {
j++; // сдвинем позицию во втором массиве
}
}
}
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
n = array_2.length, m = array_1.length, j = 0, i = 0;
while ((i < n) && (j < m)) // пока не дошли до конца массива
{
if (array_2[i] == array_1[j])
{
i++,j++;
} else {
if (array_2[i] < array_1[j]) {
array_3[k] = array_2[i];
k++;
i++; // сдвинем позицию в первом массиве
} else {
j++; // сдвинем позицию во втором массиве
}
}
}
while (i < n) {
array_3[k] = array_2[i];
k++, i++;
}
return array_3;
}
Способ предложенный 0leGG.
1 проход
function symmetric_diff_sort_arr(array_1,array_2)
{
var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = [];
while ((i < n) && (j < m)) // пока не дошли до конца массива
{
if (array_1[i] < array_2[j]) {
array_3[k] = array_1[i];
k++;
i++; // сдвинем позицию в первом массиве
} else if (array_1[i] > array_2[j]) {
array_3[k] = array_2[j];
k++;
j++; // сдвинем позицию во втором массиве
} else {
i++, j++;
}
}
while (i < n) {
array_3[k] = array_1[i];
k++, i++;
}
while (j < m) {
array_3[k] = array_2[j];
k++, j++;
}
return array_3;
}
symmetric_diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]); // на выходе [1, 2, 5, 6, 12, 24, 47]
Заключение
Мне часто приходится работать с отсортированными массивами, поэтому эти алгоритмы очень сильно ускоряют процесс. Пример реализации метода intersec_sort_arr, вы можете посмотреть в моем приложении для vk.com. С помощью данного метода я нахожу общих участников сообществ работая с отсортированными массивами, в миллионы элементов, метод справляется очень быстро. До этого использовал метод описанный в моей предыдущей статье, обработка массивов была очень медленной.