Задача с собеседования в Яндекс: Merge Two Sorted Arrays
#mergesort #twopointers
Задача. Дано два отсортированных по возрастанию массива целых чисел. Надо их смержить в один, который также будет отсортирован по возрастанию.
Решение. Эта задача повторяет существенную часть сортировки Merge Sort. Для решения нам нужно одновременно итерироваться по двум массивам. Т.е. иметь два индекса (Two Pointers). Один по первому массиву, второй по второму. Если текущий элемент из первого массива меньше, чем текущий элемент из второго, то в результирующий массив копируем элемент из первого массива и увеличиваем индекс для первого массива. В противном случае копируем элемент из второго массива и увеличиваем второй индекс. После того, как мы достигли конца одного из массивов, нам надо скопировать оставшиеся элементы из второго.
Код решения:
public static int[] merge(int[] arr1, int[] arr2) {
int i = 0;
int j = 0;
int k = 0;
int result[] = new int[arr1.length + arr2.length];
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
while (i < arr1.length) {
result[k++] = arr1[i++];
}
while (j < arr2.length) {
result[k++] = arr2[j++];
}
return result;
}
Time complexity O(n+m), Space Complexity: O(n+m). n, m - размеры массивов.