Блог

Название может сбивать с толку, и простите меня, поскольку я все еще новичок. Это часть задания HW для школы, и хотя я не ищу прямого ответа, мне нужен толчок в правильном направлении или вообще какая-либо помощь. Итак, к вопросу…

Мне нужно создать простую программу на основе кода в классе, чтобы объединить несколько отсортированных массивов в один отсортированный массив для вывода на экран. Массивы жестко запрограммированы как «тестовые примеры» для раскомментирования и проверки. Инструкции для инструкторов следующие

Используя программу слияния, разработанную в классе (см. Прикрепленный) в качестве основы, создайте версию, которая объединит 0 (ноль) в n массивов чисел. Подсказки: Сортировка массивов перед объединением Используйте метод shift для удаления первого элемента в массиве (arrayName.shift()) Чтобы создать массив массивов —> var x = [ ]; var y = [ ]; var z = [ x, y];

РЕДАКТИРОВАТЬ: я отправил инструктору электронное письмо с решением, основанным на ответе, данном @cpugourou, и его ответ заключался в том, что он не примет это решение. Цель домашнего задания — вручную объединить эти массивы.

Ниже приведена оригинальная «Программа слияния», которую мы разработали в классе

 "use strict";   // reduces chance for error

/* 
    there are 2 arrays here and this program will merge them.
    Your job is to merge zero or more arrays. Test cases include:
    1. arrays with no elements: x = [], y = [], z = [], ...
    2. 2 arrays - one with elements and one without: x = [], y = [200, 39,1]
    3. 4 arrays: x = [5, 1, 0], y = [], z = [78, 3], w = [4, 34]
*/
var x = [ 12, 5, 1], y = [ 13, 2, 3], z = [];   // x and y are input and, after processing, z has the merged arrays
var ix = 0, iy = 0, iz = 0;         // indexes to the next element

// The following sorts the arrays in ascending sequence
x.sort(function(a, b){return a - b});
y.sort(function(a, b){return a - b});

while (ix < x.length || iy < y.length){     // while arrays x or y have elements

if (ix < x.length amp;amp; iy < y.length){    // if both have elements, choose the lowest element

    if (x[ix] <= y[iy]){                // is the current element in array x less than the current element in y?
        z[iz] = x[ix];                  // choose x
        iz  ;                           // point to the next space in z
        ix  ;                           // ditto x
    } else{                             // choose y
        z[iz] = y[iy];                  
        iz  ;                           // next
        iy  ;                           // next
    }

} else if (ix < x.length){              // if only one has elements is it x?
    for (ix; ix < x.length; ix  ){      // if so, move the rest of x to z
        z[iz] = x[ix];                  // copy current element in x
        iz  ;                           // next z ... no need to increment x because the for loop does it
    }

} else if (iy < y.length){              // if only y has elements
    for (iy; iy < y.length; iy  ){      // move the rest of y to z
        z[iz] = y[iy];                  // copy
        iz  ;                           // increment z's pointer
    }
}
}

// display the resulting merged elements in the web page
var result = "<ul>";
for (var i in z){
    result  = "<li>"   z[i]   "</li>"
}
result  = "</ul>"
document.getElementById("placeAnswerHere").innerHTML=resu<

/*
Things to think about:
. This code is hard wired to merge only 2 arrays
. You will need to create an array containing all arrays to be merged. e.g. q = [x, y, z, w, and more]
. Your loop will need to find the smallest element in any of the arrays in q and move it to z (the resultant array)
. There is a method shift() to strip the first element from an array (e.g. x.shift(); removes the first element in array x)
. This is like making a pile of cafeteria trays from a variable numbers of tray stacks.
. Remember to sort all arrays first
*/
  

Итак, мой новый вопрос заключается в том, как это сделать, не написав кучу спагетти-кода?

самый быстрый и короткий, о котором я могу думать (добавлен бонус за дублирование):

 var x = [5, 1, 0], y = [2, 5, 0], z = [78, 3, 1], w = [4, 34];

function sortNumber(a,b) {
    return a - b;
}
function uniq(a) {
   return Array.from(new Set(a));
}

var d = uniq(x.concat(y,z,w).sort(sortNumber));
/* [0, 1, 2, 3, 4, 5, 34, 78] */
  

Хотя ответ cpugourou работает, он, похоже, не соответствует указанному назначению HW. Что касается назначения HW, мне неясен один вопрос: как создать общий массив массивов (например, для (i = 0; i <n; i ) aa[i] = новый массив (…) ), который, похоже, противоречит постановке задачи HW о том, что массивыэто жестко запрограммированные тестовые примеры.

Игнорируя вопрос о том, как создать общий массив жестко закодированных массивов, как только у вас есть массив отсортированных массивов, назначение HW, похоже, хочет, чтобы вы реализовали n-образное слияние с использованием массива массивов. Это означает, что нужно найти, какой массив в массиве массивов имеет наименьший элемент, и переместить этот элемент в выходной массив (добавить в выходной массив, удалить из входного массива). Когда один из n массивов очищается, этот массив удаляется из массива массивов, и вы продолжаете объединение n-1 способом. Повторяйте это до тех пор, пока не останется только 1 массив, где остальная часть этого последнего массива просто копируется (или перемещается) в выходной массив.

Обычной оптимизацией для n-образного слияния является использование кучи, но я сомневаюсь, что вы должны использовать кучу для этого назначения HW.