Как объединить два несортированных массива в другой, учитывая сложность времени - PullRequest
Новая
       5

Как объединить два несортированных массива в другой, учитывая сложность времени

0 голосов
/ 02 февраля 2020

У меня есть два или более массивов. Я хочу сформировать новый массив, который отсортирован из двух или более массивов. Я не хочу объединять массивы и сортировать их позже. Я хотел получить его на go. Учитывается сложность времени.

Подойдет любой язык программирования / алгоритм.

1 Ответ

0 голосов
/ 04 февраля 2020

, поэтому вам нужно найти для каждой позиции в новом массиве наименьшее оставшееся значение. Входными данными являются массивы a и b с n и m элементами. Найдите минимальное значение в обоих массивах. сравните два значения и установите для меньшего значения значение max в своем массиве, чтобы предотвратить его повторное обнаружение. Установите минимальное значение в c.

Псевдокод: 

merge(a[n],b[m]){
  c[n+m];
  for (i = 0, i < n+m; i++){
    aMin = getMinValue(a);
    bMin = getMinValue(b);
    if(aMin < bMin) setMinValueToMax(a,aMin)
    else setMinValueToMax(b,bMin)
    c[i] = min(aMin,bMin)
  }
  return c;
}

Здесь n - размер большего массива. GetMinValue будет работать в O (n), просто перебирать все элементы. SetMinValueToMax также будет работать в O (n), если вы не сохраните индекс. For-l oop будет в O (n). Тело для for равно 0 (3n) (2 x getMinValue + setMinValueToMax). В больших O постоянные факторы могут быть удалены, что приводит к времени выполнения O (n ^ 2).

...