Ежедневный бит (е) C ++ # 126, Общая задача на собеседовании: медиана двух отсортированных массивов.

Сегодня мы рассмотрим распространенную задачу на собеседовании: медиану двух отсортированных массивов.

Для двух отсортированных массивов вернуть медиану объединенного массива в O(log(N)), где N — общее количество элементов в двух массивах. Если общее количество элементов четное, верните среднее значение двух средних элементов.

Например, для ввода {1,3,5,7} и {1,1,2,4,8} результатом будет 3.

Прежде чем продолжить чтение решения, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/P54dKTeaa.

Решение

Из-за отсортированных входных данных эта проблема требует бинарного поиска. Однако мы должны избегать слияния двух массивов, чтобы оставаться на территории log(n).

Мы можем выполнять параллельный бинарный поиск, аналогичный поиску в 2D-пространстве. Если мы разделим оба массива на две части, мы сможем на каждой итерации удалить квадрант, который не может содержать медиану.

Наконец, мы можем обернуть эту логику и вернуть либо медиану, либо среднее значение двух средних элементов, если общая длина четна.

#include <vector>
#include <span>

int nth_element(std::span<const int> left,
                std::span<const int> right,
                int n) {  
    if (left.empty()) return right[n];
    if (right.empty()) return left[n];

    int left_mid = left.size()/2;
    int right_mid = right.size()/2;

    if (left[left_mid] <= right[right_mid]) {
    // at least left_mid + right_mid + 1
    // elements before right[right_mid]
        if (n < left_mid + right_mid + 1)
            // the nth element is strictly before right[right_mid]
            return nth_element(left, right.subspan(0, right_mid), n);
        else
            // the nth element is strictly after left[left_mid]
            return nth_element(left.subspan(left_mid + 1), right,
                               n - left_mid - 1);
    } else /* if (left[left_mid] > right[right_mid]) */ {
    // at least left_mid + right_mid + 1
    // elements before left[left_mid]
        if (n < left_mid + right_mid + 1)
            // the nth element is strictly before left[left_mid]
            return nth_element(left.subspan(0, left_mid), right, n);
        else
            // the nth element is strictly after right[right_mid]
            return nth_element(left, right.subspan(right_mid + 1), 
                               n - right_mid - 1);
    }
}

double median_of_two_arrays(const std::vector<int>& nums1, 
                            const std::vector<int>& nums2) {
    int mid = (nums1.size()+nums2.size())/2;
    int n = nth_element(nums1, nums2, mid);
    if ((nums1.size() + nums2.size()) % 2 == 0)
        return (nth_element(nums1, nums2, mid - 1) + n) / 2.0;
    return n;
}

Откройте решение в Compiler Explorer.