Вам даны два отсортированных массива, 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.
Чтобы эффективно решить эту проблему, вы можете использовать подход, основанный на бинарном поиске. Поскольку оба массива отсортированы, вы можете сравнивать медианы двух массивов и принимать решения на основе сравнения, чтобы сузить область поиска.
Вот набросок алгоритма:
- Найдите меньший массив между nums1 и nums2 и назначьте его переменной с именем «smaller». Кроме того, найдите больший массив и назначьте его переменной с именем «больше».
- Инициализируйте два указателя, «левый» и «правый», для меньшего массива «меньше». Установите «слева» на 0 и «справа» на длину «меньшего» массива.
- Выполните двоичный поиск в «меньшем» массиве, обновляя указатели «левый» и «правый» до тех пор, пока «левый» не станет меньше или равен «правому».
- Вычислите точки раздела «partitionX» и «partitionY» в «меньшем» и «большом» массивах соответственно на основе «левого» и «правого» указателей.
- Сравните элементы в разделах «partitionX-1» и «partitionX» в «меньшем» массиве и аналогичным образом сравните элементы в «partitionY-1» и «partitionY» в «большем» массиве.
- На основе сравнений отрегулируйте указатели «влево» и «вправо», чтобы сузить пространство поиска в «меньшем» массиве.
- Повторяйте шаги 4–6, пока не найдете правильные точки разбиения, так что элементы по обе стороны от точек разбиения удовлетворяют условию медианы (т. е. все элементы с левой стороны меньше, чем все элементы с правой стороны).
- Как только вы найдете правильные точки раздела, рассчитайте медиану на основе элементов в точках раздела и верните результат.
- Если «меньший» массив имеет четное количество элементов, возьмите среднее значение максимума элементов с левой стороны от точек разбиения и минимума элементов с правой стороны. Если «меньший» массив имеет нечетное количество элементов, верните элемент в точке раздела в качестве медианы.
Используя подход, основанный на бинарном поиске, вы можете достичь желаемой сложности времени выполнения 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; } } }