Comments 9
Очень интересно, спасибо за статью.
Симметрическую разность тоже можно за один проход посчитать, просто отслеживая минимальный элемент из имеющихся двух списков:
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;
}
отлично, добавил предложенный вами способ в статью.
Можно две строчки изменить в функции объединения и получится функция симметрической разности
if (array_1[i] == array_2[j])
{
//array_3[k] = array_1[i];
//k++,
i++,j++;
}Ну да, по сути мы разбиваем элементы исходных множеств A и B на три типа — «есть только в A» (ветка a[i] < b[j]), «есть только в B» (ветка a[i] > b[j]), «есть и в A, и в B» (ветка a[i] == b[j]). Все перечисленные функции есть комбинации этих трёх непересекающихся множеств, содержащих в себе все элементы исходных.
Упорядоченные не значит отсортированные. Будут ли алгоритмы работать на несортированных данных?
Алгоритм для симметрической разности(тот который «2 прохода»): объединение двух разностей, можно было бы так и записать:
Алгоритм для симметрической разности(тот который «2 прохода»): объединение двух разностей, можно было бы так и записать:
function symmetric_diff_sort_arr(array_1,array_2){
var arr_diff1=diff_sort_arr(array_1,array_2)
var arr_diff2=diff_sort_arr(array_2,array_1)
//return sum_sort_arr(arr_diff1,arr_diff2)
return arr_diff1.concat(arr_diff2)
}
Никогда не понимал, зачем люди пишут так:
Верхнее условие абсолютно не нужно. Если оно не выполняется, то цикл всё равно не выполнится. А если выполняется, то в начале цикла будет два раза одинаковая проверка.
И да, в JavaScript лучше сравнивать по ===, если у вас нет хорошей причины так не делать.
if (j < m)
{
while (j < m) {
...
}
}Верхнее условие абсолютно не нужно. Если оно не выполняется, то цикл всё равно не выполнится. А если выполняется, то в начале цикла будет два раза одинаковая проверка.
И да, в JavaScript лучше сравнивать по ===, если у вас нет хорошей причины так не делать.
Sign up to leave a comment.
Бинарные операции над упорядоченными множествами