Javascript, Слияние двух отсортированных массивов: Может кто-нибудь сказать, пожалуйста, почему это не дает правильную сортировку слиянием?

Question

Я попытался объединить два массива, но получаю вывод [0, 3, 3, 4, 4]

function mergeSortedArrays(arr1, arr2) {
  var i = 0;
  var j = 0;
  var arr3 = [];

  if (arr1 === undefined || arr1.length == 0) {
    return arr2;
  }

  if (arr2 === undefined || arr2.length == 0) {
    return arr1;
  }

  while (i < arr1.length - 1 && j < arr2.length - 1) {
    if (arr1[i] < arr2[j]) {
      arr3.push(arr1[i]);
      i++;
    } else {
      arr3.push(arr2[j]);
      j++;
    }
  }
  return arr3;
}

console.log(mergeSortedArrays([0, 3, 4, 31], [3, 4, 6, 30]));

Для этого примера я знаю, что не учел случай, когда массивы имеют разный размер, но это для более поздней проблемы.Код в настоящее время даже не работает для основного случая.Он не повторяется полностью и ломается на полпути.Может кто-нибудь, пожалуйста, решить эту проблему.Я работал с циклом while, но код все еще не работает.

Answer 1

Вы делаете две ошибки.

• В проверке состояния цикла while для length массива не length - 1.Это не добавит последние элементы обоих массивов.
• Ваш цикл while закончится, когда один из массивов будет полностью зациклен из-за &&.Так что через некоторое время добавьте остальные элементы другого массива.

function mergeSortedArrays(arr1, arr2) {
  var i = 0;
  var j = 0;
  var arr3 = [];

  if (arr1 === undefined || arr1.length == 0) {
    return arr2;
  }

  if (arr2 === undefined || arr2.length == 0) {
    return arr1;
  }

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      arr3.push(arr1[i]);
      i++;
    } else {
      arr3.push(arr2[j]);
      j++;
    }
    
  }
  if(i === arr1.length){
      return arr3.concat(arr2.slice(j))
    }
    else if(j === arr2.length){
      return arr3.concat(arr1.slice(i))
    }
}

console.log(mergeSortedArrays([0, 3, 4, 31], [3, 4, 6, 30]));

Answer 2

Существует простое однострочное решение, которое включает курорт.Использование параметров по умолчанию для работы с неопределенными массивами и оператора распространения для заполнения нового массива двумя объединяющимися массивами.Массив результатов просто нужно отсортировать и затем вернуть.

const mergeSorted = (a1 = [], a2 = []) => [...a1, ...a2].sort((a, b) => a - b);

Пример

const mergeSorted= (a1 = [], a2 = []) => [...a1, ...a2].sort((a, b) => a - b);
console.log(mergeSorted([0, 3, 4, 31], [3, 4, 6, 30]).join(", "));

Или без сортировки и использования параметров по умолчанию, чтобы избежать необходимости проверять массивы на неопределенные значения

function mergeSorted(a1 = [], a2 = []) {
    const res = [];
    var idx1 = 0, idx2 = 0;
    while (idx1 < a1.length || idx2 < a2.length) {
        if (idx1 < a1.length && idx2 < a2.length) {
           res.push(a1[idx1] < a2[idx2] ? a1[idx1++] : a2[idx2++]);
        } else {
           res.push(idx1 < a1.length ? a1[idx1++] : a2[idx2++]);
        }
    }
    return res;
}

Пример

function mergeSorted(a1 = [], a2 = []) {
    const res = [], l1 = a1.length, l2 = a2.length;
    var i1 = 0, i2 = 0;
    while (i1 < l1 || i2 < l2) {
        if (i1 < l1 && i2 < l2) { res.push(a1[i1] < a2[i2] ? a1[i1++] : a2[i2++]) }
        else { res.push(i1 < l1 ? a1[i1++] : a2[i2++]) }
    }
    return res;
}
console.log(mergeSorted([0, 3, 4, 31, 99], [3, 4, 6, 30]).join(", "));

Answer 3

Прежде всего, цикл должен повторяться до arr1.lenght и arr2.lenght, а не до длины - 1,

while (i < arr1.length  && j < arr2.length )

Кроме того, после прерывания цикла причиной является либо один из массивовПеременные цикла имеют ложное условие, перед возвратом массива необходимо проверить, остались ли значения, которые еще не вставлены. Это важно .

Вы можете сделать это:

arr3.concat(arr1.slice(i)).concat(arr2.slice(j));

Надеюсь, это поможет.

Answer 4

В вашем коде отсутствуют две вещи:

1. Цикл while работает для i < arr1.length - 1 для arr1 и j < arr2.length - 1 для arr2.Это означает, что он будет работать до 3-го индекса arr1 и arr2.Таким образом, последний индекс не будет выполняться в цикле.Таким образом, вы должны рефакторинг цикла как i < arr1.length для arr1 и j < arr2.length для arr2.

2. Следующая недостающая вещь, вам нужно добавить цикл для оставшихся элементов оставшихсямассив.Это означает, что когда вы выполняете код, все элементы одного цикла будут помещены в arr3, тогда один элемент другого массива будет пропущен, и он не будет вставлен в arr3 (для одинаковой длины обоих массивов).и / или будет пропущено более одного элемента другого массива (для различной длины обоих массивов).Поэтому вам нужно поместить остальные элементы другого массива в arr3.

Я добавил рефакторированный код вашего кода.

function mergeSortedArrays(arr1, arr2) {
    var i = 0;
    var j = 0;
    var arr3 = [];

    if (arr1 === undefined || arr1.length == 0) {
        return arr2;
    }

    if (arr2 === undefined || arr2.length == 0) {
        return arr1;
    }

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            arr3.push(arr1[i]);
            i++;
        } else {
            arr3.push(arr2[j]);
            j++;
        }
    }
    while (i < arr1.length) {
        arr3.push(arr1[i]);
        i++;
    }
    while (j < arr2.length) {
        arr3.push(arr2[j]);
        j++;
    }
    return arr3;
}

OR

вы можете использовать оператор распространения для объединения обоих массивов, а затем вы можете использовать метод сортировки JS.

function mergeTwo(arr1, arr2) {
  let result = [...arr1, ...arr2];
  return result.sort((a,b) => a-b);
}

Answer 5

Это работает:

function mergeTwoSortedArrays(arr1, arr2) {
  let merged = [];
  let index1 = 0;
  let index2 = 0;
  let current = 0;

  while (current < (arr1.length + arr2.length)) {

    let isArr1Depleted = index1 >= arr1.length;
    let isArr2Depleted = index2 >= arr2.length;

    if (!isArr1Depleted && (isArr2Depleted || (arr1[index1] < arr2[index2]))) {
      merged[current] = arr1[index1];
      index1++;
    } else {
      merged[current] = arr2[index2];
      index2++;
    }

    current++;
  }

  return merged;
}

Для получения дополнительной информации: https://wsvincent.com/javascript-merge-two-sorted-arrays/

Answer 6

В условии while, когда индексы i или j достигают длины соответствующего массива, завершает цикл, возвращая массив меньшей длины.