Вам даны два отсортированных массива, nums1 и nums2, с размерами m и n соответственно. Ваша задача — найти медиану двух отсортированных массивов. Общая сложность вашего решения во время выполнения должна быть O (log (m + n)).

Вот два примера, иллюстрирующих проблему:

Пример 1: nums1 = [1, 3] nums2 = [2] Медиана nums1 и nums2 равна 2,0.

Пример 2: nums1 = [1, 2] nums2 = [3, 4] Медиана nums1 и nums2 равна (2 + 3)/2 = 2,5.

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

Вот набросок алгоритма:

  1. Найдите меньший массив между nums1 и nums2 и назначьте его переменной с именем «smaller». Кроме того, найдите больший массив и назначьте его переменной с именем «больше».
  2. Инициализируйте два указателя, «левый» и «правый», для меньшего массива «меньше». Установите «слева» на 0 и «справа» на длину «меньшего» массива.
  3. Выполните двоичный поиск в «меньшем» массиве, обновляя указатели «левый» и «правый» до тех пор, пока «левый» не станет меньше или равен «правому».
  4. Вычислите точки раздела «partitionX» и «partitionY» в «меньшем» и «большом» массивах соответственно на основе «левого» и «правого» указателей.
  5. Сравните элементы в разделах «partitionX-1» и «partitionX» в «меньшем» массиве и аналогичным образом сравните элементы в «partitionY-1» и «partitionY» в «большем» массиве.
  6. На основе сравнений отрегулируйте указатели «влево» и «вправо», чтобы сузить пространство поиска в «меньшем» массиве.
  7. Повторяйте шаги 4–6, пока не найдете правильные точки разбиения, так что элементы по обе стороны от точек разбиения удовлетворяют условию медианы (т. е. все элементы с левой стороны меньше, чем все элементы с правой стороны).
  8. Как только вы найдете правильные точки раздела, рассчитайте медиану на основе элементов в точках раздела и верните результат.
  9. Если «меньший» массив имеет четное количество элементов, возьмите среднее значение максимума элементов с левой стороны от точек разбиения и минимума элементов с правой стороны. Если «меньший» массив имеет нечетное количество элементов, верните элемент в точке раздела в качестве медианы.

Используя подход, основанный на бинарном поиске, вы можете достичь желаемой сложности времени выполнения O (log (m + n)).

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int counter=0;
    int flag1=0;
    int flag2=0;
    int target=(nums1Size+nums2Size)/2;
    int mid=0;
 
    if((nums1Size+nums2Size)&0x01)
      target++;
 
    //check if nums1 or nums2 is null
    if(nums1Size==0)
    {
        if(nums2Size==1)
          return nums2[0];
 
        if((nums1Size+nums2Size)&0x01)
          return nums2[target-1];
        else
          return ((double)nums2[target]+(double)nums2[target-1])/2;
    }
 
    if(nums2Size==0)
    {
        if(nums1Size==1)
          return nums1[0];
 
        if((nums1Size+nums2Size)&0x01)
          return nums1[target-1];
        else
          return ((double)nums1[target]+(double)nums1[target-1])/2;
    }
 
    printf("target:%d\n",target);
 
    while(counter!=target)
    {
        counter++;
        if(flag1>=nums1Size)
        {
            mid=nums2[flag2];
            flag2++;
            continue;
        }
        if(flag2>=nums2Size)
        {
            mid=nums1[flag1];
            flag1++;
            continue;
        }
 
        if(nums1[flag1]>nums2[flag2])
        {
            mid=nums2[flag2];
            flag2++;
        }else
        {
            mid=nums1[flag1];
            flag1++;
        }
    }
 
    if((nums1Size+nums2Size)&0x01)
       return mid;
    else
    {
        if(flag1 == nums1Size)
          return ((double)mid+(double)nums2[flag2])/2;
        if(flag2 == nums2Size)
          return ((double)mid+(double)nums1[flag1])/2;
 
        if(nums1[flag1]>nums2[flag2])
        {
            return ((double)mid+(double)nums2[flag2])/2;
        }else
        {
            return ((double)mid+(double)nums1[flag1])/2;
        }
    }
}