Постановка проблемы:

Имея два отсортированных массива nums1 и nums2 размером m и n соответственно, верните медиану двух отсортированных массивов.

Общая сложность времени выполнения должна быть O(log (m+n)).

Пример 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Пример 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Ограничения:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Решение:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double[] arr = new double[nums1.length + nums2.length];
        int i = 0; 
        int j = 0;
        int k = 0;
        while( i < nums1.length && j < nums2.length){
            if(nums1[i] < nums2[j]){
                arr[k] = nums1[i];
                i++;
            }else{
                arr[k] = nums2[j];
                j++;
            }
            k++;
        }
        while(i < nums1.length){
            arr[k] = nums1[i];
            i++;
            k++;
        }
        while(j < nums2.length){
            arr[k] = nums2[j];
            k++;
            j++;
        }

        double value = 0;
        if(arr.length % 2 == 0){
            double prev = arr[(arr.length/2)-1];
            double next = arr[arr.length/2];
            value = (prev+next)/2;

        }else{
            value = arr[arr.length/2];

        }
        return value;

Временная сложность: O(m+n), где m и n — длины входных массивов nums1 и nums2 соответственно.

Сложность пространства: O(m+n), где m и n — длины входных массивов nums1 и nums2, используемых для создания нового массива.

Этот код принимает два отсортированных массива nums1 и nums2 в качестве входных данных и возвращает медианное значение объединенного отсортированного массива. Алгоритм создает новый массив arr с длиной, равной сумме длин nums1 и nums2. Затем он перебирает как nums1, так и nums2, используя два указателя i и j соответственно, сравнивая элементы с одним и тем же индексом и добавляя меньший элемент к arr. Индекс arr для добавления элемента хранится в переменной k. Указатели i и j увеличиваются в зависимости от того, какой элемент массива был добавлен к arr, а k также увеличивается, чтобы указывать на следующий индекс в arr.

После слияния обоих массивов в одном из входных массивов могут остаться элементы. Поэтому выполняются еще два цикла, чтобы добавить эти оставшиеся элементы в конец arr.

Наконец, вычисляется и возвращается медиана объединенного массива. Если длина arr четная, медиана является средним значением двух средних элементов. В противном случае медиана — это просто средний элемент отсортированного массива.

Важно отметить, что этот код предполагает, что оба входных массива отсортированы в порядке возрастания. Если это не так, функция не вернет правильный результат.

Оптимальный подход:

Использование бинарного поиска:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    if (n > m) {
        return findMedianSortedArrays(nums2, nums1);
    }
    int left = 0;
    int right = n;
    int i, j;
    while (left <= right) {
        i = (left + right) / 2;
        j = (n + m + 1) / 2 - i;
        if (i < n && j > 0 && nums2[j-1] > nums1[i]) {
            left = i + 1;
        } else if (i > 0 && j < m && nums1[i-1] > nums2[j]) {
            right = i - 1;
        } else {
            int maxLeft = 0;
            if (i == 0) {
                maxLeft = nums2[j-1];
            } else if (j == 0) {
                maxLeft = nums1[i-1];
            } else {
                maxLeft = Math.max(nums1[i-1], nums2[j-1]);
            }
            if ((n + m) % 2 == 1) {
                return maxLeft;
            }
            int minRight = 0;
            if (i == n) {
                minRight = nums2[j];
            } else if (j == m) {
                minRight = nums1[i];
            } else {
                minRight = Math.min(nums1[i], nums2[j]);
            }
            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0; // should never be reached
}

Временная сложность: O(log(min(N,M)))

Пространственная сложность: O(1).

В этом решении используется двоичный поиск, чтобы найти точку раздела двух массивов, чтобы элементы слева от раздела были меньше или равны элементам справа. Эта точка раздела также дает медиану двух массивов. Если общее количество элементов в двух массивах нечетное, то медианой является максимальный элемент слева. Если общее количество элементов в двух массивах четное, то медиана представляет собой среднее значение максимального элемента слева и минимального элемента справа.

Код сначала проверяет, больше ли длина nums1 длины nums2, и если да, меняет их местами, чтобы убедиться, что nums1 меньше из двух. Затем он инициализирует левый и правый указатели для бинарного поиска.

Цикл while выполняется до тех пор, пока левый указатель не станет меньше или равен правому указателю. Внутри цикла точка раздела вычисляется с использованием i и j, а элементы по обе стороны от раздела проверяются, чтобы убедиться, что они расположены в правильном порядке. Если нет, левый или правый указатель корректируется соответствующим образом. Если элементы расположены в правильном порядке, максимальный элемент слева и минимальный элемент справа вычисляются и возвращаются как медиана.

Если цикл завершится без нахождения допустимой точки раздела, функция вернет 0,0 (чего на практике быть не должно).

Этот алгоритм имеет временную сложность O(log(min(n,m))) и пространственную сложность O(1).