Найдите медиану двух заданных векторов

Даны два вектора a и b разного размера, где массив a содержит m элементов, а массив b содержит n элементов. Задача состоит в том, чтобы найти медиану двух векторов. Эта задача является расширением задачи о медиане двух отсортированных массивов разного размера.

Пример:

Input: a = {1, 4}
          b = {2}

Output: The median is 2.

Explanation: 
The merged vector = {1, 2, 4} 
So, the median is 2.

Input: a = {1, 2}
           b = {3, 5}

Output: The median is 2.50000

Explanation: 
The merged vector = {1, 2, 3, 5} 
So, the median is (2 + 3) / 2 = 2.5.

Подход:

1. Инициализируйте вектор a.
2. Инициализировать вектор b.
3. Создайте новый вектор размера a + b .
4. Повторите с помощью цикла первый вектор и сохраните данные во вновь созданном векторе и аналогично для второго вектора после повторения первого вектора.
5. Объединил оба отсортированных вектора во вновь созданный вектор с помощью STL-функции merge().
6. Найдите медиану для четных и нечетных размеров и верните ее.

Ниже приведена реализация описанного выше подхода на C++:

Сложность:

Сложность времени: O(m + n), так как для объединения обоих векторов требуется время O(m+n).
Сложность пространства: O(1), так как дополнительное пространство не требуется.