Разбор задачи 4. Median of Two Sorted Arrays LeetCode.com

Медиана двух отсортированных массивов

Учитывая два отсортированных массива nums1 и nums2 размер m и n соответственно, вернуть медиану двух отсортированных массивов.

Общая сложность времени выполнения должна быть O(log (m+n)).

Пример 1:

Ввод: nums1 = [1,3], nums2 = [2]
 Вывод: 2,00000
 Объяснение: объединенный массив = [1,2,3] и медиана равна 2.

Пример 2:

Ввод: nums1 = [1,2], nums2 = [3,4]
 Вывод: 2,50000
 Объяснение: объединенный массив = [1,2,3,4] и медиана (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

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

Идея алгоритма заключается в том, что мы хотим разделить оба массива так, чтобы элементы справа и слева от разделительной линии были одинаковые или различались только на одну позицию. Кроме того, мы хотим, чтобы все элементы слева от линии были меньше, чем все элементы справа от нее.

Для массивов nums1 и nums2 мы можем выбрать разделительные линии i и j таким образом, чтобы i + j = (m+n+1)/2 и чтобы все элементы слева от i и j были меньше или равны медиане M и все элементы справа от i и j были больше или равны медиане M.

Теперь, чтобы получить медиану, мы должны найти максимальный элемент слева от линии (lmax) и минимальный элемент справа от линии (rmin). Если m+n является нечетным числом, то медиана равна max(lmax, rmin). Если m+n является четным числом, то медиана равна (max(lmax, rmin) + min(rmin, lmax))/2.

Решение задачи «Медиана двух отсортированных массивов» пример кода на Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # определяем длины двух массивов nums1 и nums2
        m, n = len(nums1), len(nums2)
        
        # если m > n, то меняем местами nums1 и nums2, m и n
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        
        # инициализируем переменные imin, imax и half_len
        imin, imax, half_len = 0, m, (m + n + 1) // 2
        
        # запускаем цикл while с условием imin <= imax
        while imin <= imax:
            # определяем переменные i и j
            i = (imin + imax) // 2
            j = half_len - i
            
            # если i < m и nums2[j-1] > nums1[i], то увеличиваем значение imin на 1
            if i < m and nums2[j-1] > nums1[i]:
                imin = i + 1
            # если i > 0 и nums1[i-1] > nums2[j], то уменьшаем значение imax на 1
            elif i > 0 and nums1[i-1] > nums2[j]:
                imax = i - 1
            # в противном случае
            else:
                # если i = 0, то lmax равен nums2[j-1]
                if i == 0:
                    lmax = nums2[j-1]
                # если j = 0, то lmax равен nums1[i-1]
                elif j == 0:
                    lmax = nums1[i-1]
                # иначе lmax равен максимальному из nums1[i-1] и nums2[j-1]
                else:
                    lmax = max(nums1[i-1], nums2[j-1])
                
                # если (m + n) % 2 == 1, то медиана равна lmax
                if (m + n) % 2 == 1:
                    return lmax
                
                # если i = m, то rmin равен nums2[j]
                if i == m:
                    rmin = nums2[j]
                # если j = n, то rmin равен nums1[i]
                elif j == n:
                    rmin = nums1[i]
                # иначе rmin равен минимальному из nums1[i] и nums2[j]
                else:
                    rmin = min(nums1[i], nums2[j])
                
                # медиана равна среднему значению lmax и rmin
                return (lmax + rmin) / 2

Решение задачи «Медиана двух отсортированных массивов» пример кода на Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		// инициализация переменных m и n с длинами массивов nums1 и nums2 соответственно
        int m = nums1.length;
        int n = nums2.length;
		// проверка, что длина массива nums1 не больше длины массива nums2, если это так,
		// то меняем массивы местами и пересчитываем длины
        if (m > n) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            m = nums1.length;
            n = nums2.length;
        }
		// инициализация переменных для бинарного поиска медианы
        int imin = 0;
        int imax = m;
        int half_len = (m + n + 1) / 2;
		// бинарный поиск медианы
        while (imin <= imax) {
			// разбиваем nums1 на две части в точке i
            int i = (imin + imax) / 2;
			// разбиваем nums2 на две части в точке j
            int j = half_len - i;
            // если j > 0 и nums2[j-1] > nums1[i], значит нужно уменьшить i, чтобы увеличить j
			if (i < m && nums2[j - 1] > nums1[i]) {
				imin = i + 1;
			} 
			// если i > 0 и nums1[i-1] > nums2[j], значит нужно увеличить i, чтобы уменьшить j
			else if (i > 0 && nums1[i - 1] > nums2[j]) {
				imax = i - 1;
			} 
			// иначе найдена правильная разбивка, находим медиану
			else {
				int lmax = 0;
				if (i == 0) {
					lmax = nums2[j - 1];
				} else if (j == 0) {
					lmax = nums1[i - 1];
				} else {
					lmax = Math.max(nums1[i - 1], nums2[j - 1]);
				}
				// если суммарная длина массивов нечётная, медиана - максимальный элемент левой части
				if ((m + n) % 2 == 1) {
					return lmax;
				}
				int rmin = 0;
				if (i == m) {
					rmin = nums2[j];
				} else if (j == n) {
					rmin = nums1[i];
				} else {
					rmin = Math.min(nums1[i], nums2[j]);
				}
				// если суммарная длина массивов чётная, медиана - среднее максимального элемента левой
				// части и минимального элемента правой части
				return (lmax + rmin) / 2.0;
			}
		}
        return 0.0;
    }
}

Решение задачи «Медиана двух отсортированных массивов» пример кода на C++

// объявление класса Solution и его метода findMedianSortedArrays
class Solution {
public:
    // определение метода для поиска медианы двух отсортированных массивов
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // получаем размеры массивов
        int m = nums1.size();
        int n = nums2.size();
        // если размер nums1 больше, чем nums2, то меняем их местами и обновляем значения m и n
        if (m > n) {
            swap(nums1, nums2);
            swap(m, n);
        }
        // устанавливаем начальные значения переменных
        int imin = 0;
        int imax = m;
        int half_len = (m + n + 1) / 2;
        // выполняем бинарный поиск
        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = half_len - i;
            // если элемент nums2[j - 1] больше, чем nums1[i], увеличиваем значение i
            if (i < m && nums2[j - 1] > nums1[i]) {
                imin = i + 1;
            } 
            // если элемент nums1[i - 1] больше, чем nums2[j], уменьшаем значение i
            else if (i > 0 && nums1[i - 1] > nums2[j]) {
                imax = i - 1;
            } 
            // в этом случае мы нашли медиану
            else {
                int lmax = 0;
                // вычисляем левую часть медианы
                if (i == 0) {
                    lmax = nums2[j - 1];
                } else if (j == 0) {
                    lmax = nums1[i - 1];
                } else {
                    lmax = max(nums1[i - 1], nums2[j - 1]);
                }
                // если сумма размеров массивов нечетная, возвращаем lmax
                if ((m + n) % 2 == 1) {
                    return lmax;
                }
                int rmin = 0;
                // вычисляем правую часть медианы
                if (i == m) {
                    rmin = nums2[j];
                } else if (j == n) {
                    rmin = nums1[i];
                } else {
                    rmin = min(nums1[i], nums2[j]);
                }
                // если сумма размеров массивов четная, возвращаем среднее значение
                return (lmax + rmin) / 2.0;
            }
        }
        // если массивы не пересекаются, возвращаем 0.0
        return 0.0;
    }
};

Решение задачи «Медиана двух отсортированных массивов» пример кода на JavaScript

// объявление функции с двумя аргументами, которые представляют собой два отсортированных массива
var findMedianSortedArrays = function(nums1, nums2) {
    // определение длины каждого массива
    let m = nums1.length;
    let n = nums2.length;
    // если длина первого массива больше длины второго, меняем их местами
    if (m > n) {
        [nums1, nums2] = [nums2, nums1];
        [m, n] = [n, m];
    }
    // определение минимального и максимального индексов массива nums1, используемых в дальнейшем
    let imin = 0;
    let imax = m;
    // определение половины длины объединенных массивов
    let half_len = Math.floor((m + n + 1) / 2);
    // бинарный поиск по массивам для нахождения медианы
    while (imin <= imax) {
        // определение индекса i в nums1
        let i = Math.floor((imin + imax) / 2);
        // определение индекса j в nums2
        let j = half_len - i;
        // если nums2[j - 1] больше nums1[i], увеличиваем значение i
        if (i < m && nums2[j - 1] > nums1[i]) {
            imin = i + 1;
        // если nums1[i - 1] больше nums2[j], уменьшаем значение i
        } else if (i > 0 && nums1[i - 1] > nums2[j]) {
            imax = i - 1;
        } else {
            // максимальный элемент слева от медианы
            let lmax = 0;
            if (i == 0) {
                lmax = nums2[j - 1];
            } else if (j == 0) {
                lmax = nums1[i - 1];
            } else {
                lmax = Math.max(nums1[i - 1], nums2[j - 1]);
            }
            // если длина объединенных массивов нечетная, возвращаем lmax
            if ((m + n) % 2 == 1) {
                return lmax;
            }
            // минимальный элемент справа от медианы
            let rmin = 0;
            if (i == m) {
                rmin = nums2[j];
            } else if (j == n) {
                rmin = nums1[i];
            } else {
                rmin = Math.min(nums1[i], nums2[j]);
            }
            // если длина объединенных массивов четная, возвращаем среднее значение максимального элемента слева и минимального элемента справа
            return (lmax + rmin) / 2;
        }
    }
};

Решение задачи «Медиана двух отсортированных массивов» пример кода на C#

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // длина первого массива
        int m = nums1.Length;
        // длина второго массива
        int n = nums2.Length;
        
        // если первый массив длиннее, меняем их местами
        if (m > n) {
            return FindMedianSortedArrays(nums2, nums1); 
        }
        
        // левая граница
        int left = 0;
        // правая граница
        int right = m;
        
        // бинарный поиск
        while (left <= right) {
            // позиция разделителя в первом массиве
            int partitionX = (left + right) / 2;
            // позиция разделителя во втором массиве
            int partitionY = (m + n + 1) / 2 - partitionX;
            
            // максимальный элемент слева от разделителя в первом массиве
            int maxLeftX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
            // минимальный элемент справа от разделителя в первом массиве
            int minRightX = (partitionX == m) ? int.MaxValue : nums1[partitionX];
            
            // максимальный элемент слева от разделителя во втором массиве
            int maxLeftY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];
            // минимальный элемент справа от разделителя во втором массиве
            int minRightY = (partitionY == n) ? int.MaxValue : nums2[partitionY];
            
            // если условие выполнено, то разделитель найден
            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                // если количество элементов в массивах четное
                if ((m + n) % 2 == 0) {
                    // медиана - среднее значение двух элементов, соседних с разделителем
                    return (Math.Max(maxLeftX, maxLeftY) + Math.Min(minRightX, minRightY)) / 2.0;
                } else {
                    // медиана - максимальный элемент слева от разделителя
                    return Math.Max(maxLeftX, maxLeftY);
                }
            // если максимальный элемент слева от разделителя в первом массиве больше минимального элемента справа от разделителя во втором массиве	
            } else if (maxLeftX > minRightY) {
                // ищем разделитель левее текущей позиции
                right = partitionX - 1;
            } else {
                // ищем разделитель правее текущей позиции
                left = partitionX + 1;
            }
        }
        
        // если разделитель не найден
        throw new ArgumentException("Invalid argument");
    }
}

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

Понравилась статья? Поделиться с друзьями:
Подписаться
Уведомить о
guest

0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x