Вопрос:

ссылка: https://leetcode.com/problems/median-of-two-sorted-arrays/

Имея два отсортированных массива 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

Решение:

Подход: Конечно! Предоставленный код является решением проблемы нахождения медианы двух отсортированных массивов, nums1 и nums2. Вот разбивка кода:

  1. Метод findMedianSortedArrays принимает два отсортированных целочисленных массива nums1 и nums2 в качестве входных данных и возвращает медианное значение как двойное.
  2. Он инициализирует переменные m и n для хранения длин nums1 и nums2 соответственно.
  3. Массив temp создается с размером, равным сумме длин nums1 и nums2. Этот массив будет использоваться для объединения двух отсортированных массивов.
  4. Переменные i, j и k инициализируются для отслеживания индексов nums1, nums2 и temp соответственно.
  5. Код обрабатывает крайние случаи, когда один из массивов имеет только один элемент. Если temp имеет только один элемент, а nums1 имеет один элемент, этот элемент возвращается как медиана. Точно так же, если temp имеет только один элемент, а nums2 имеет один элемент, этот элемент возвращается как медиана.
  6. Затем код объединяет два отсортированных массива nums1 и nums2 в массив temp с помощью цикла while. Он сравнивает элементы с текущими индексами i и j из nums1 и nums2 соответственно. Меньший элемент добавляется к temp, а соответствующий индекс (i или j) увеличивается. Индекс k также увеличивается, чтобы отслеживать позицию в temp.
  7. После объединения массивов любые оставшиеся элементы в nums1 или nums2 добавляются в temp с помощью двух отдельных циклов while.
  8. Переменная mid вычисляется как сумма длин nums1 и nums2, деленная на 2. Она представляет средний индекс temp и используется для нахождения медианы.
  9. Если общее количество элементов в temp четное (temp.length % 2 == 0), а mid больше 0, это означает, что есть два средних элемента. В этом случае медиана рассчитывается путем получения среднего значения в точках temp[mid] и temp[mid - 1].
  10. Если общее количество элементов в temp нечетное, медиана — это просто значение в temp[mid].
  11. Наконец, медианное значение возвращается как двойное.
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] temp = new int[m+n];
        int i=0, j=0, k=0;
        
        if(temp.length == 1 && m ==1){
            return nums1[0];
        }
        if(temp.length == 1 && n==1){
            return nums2[0];
        }
        
        while(i<m && j<n){
            if(nums1[i] < nums2[j]){
                temp[k] = nums1[i];
                i++;
            }else{
                temp[k] = nums2[j];
                j++;
            }
            k++;
        }
        while(i<m){
            temp[k] = nums1[i];
            i++;
            k++;
        }
        while(j<n){
            temp[k] = nums2[j];
            j++;
            k++;
        }
        
        int mid = m+n;
        mid = mid/2;
        if(temp.length%2 == 0 && mid > 0){
            double ans = temp[mid] + temp[mid-1];
            ans = ans/2;
            return ans;
        }else{
            return temp[mid];
        }
    }
}

Временная сложность: O(m+n)

Космическая сложность: O(m+n)

Заключение:

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

Удачного кодирования.