Ежедневный бит (е) 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.