Сложность: Средняя, Вопросы: Facebook, Microsoft, Ключевой вывод после прочтения этого блога:Вы научитесь решать проблемы с помощью одного цикла и подход разделяй и властвуй. В подходе с одним циклом мы увеличиваем цикл на 2, чтобы решить проблему, используя минимальное количество сравнений.
Понимание проблемы
Дан массив X[] размера n. Напишите программу для нахождения максимального и минимального элементов в массиве. Нашей целью было бы решить эту проблему, используя минимальное количество сравнений.
Примеры
Ввод: X[] = [4, 2, 0, 8, 20, 9, 2], Вывод: max = 20, min = 0
Ввод: X[] = [-8, - 3, -10, -32, -1], Выход: макс = -1, мин = -32
Подход грубой силы: увеличение цикла на 1
- Мы инициализируем две переменные, max и min, первым элементом.
- Теперь мы проходим по массиву и сравниваем каждый элемент с min и max. Если X[i] ‹ min, мы обновляем min на X[i]. В противном случае, если X[i] › max, мы обновляем max на X[i].
- К концу цикла минимальный и максимальный элементы массива будут сохранены в min и max. Чтобы вернуть эти два значения, мы берем дополнительный массив output[] размера 2 (мы сохраняем максимум на выходе[0] и минимум на выходе[1]).
Псевдокод алгоритма
Алгоритм анализа
Худший случай будет иметь место, когда массив отсортирован в порядке убывания. В этой ситуации мы будем делать два сравнения на каждой итерации, то есть первое, если утверждение будет ложным, а второе, если утверждение будет истинным. Таким образом, общее количество сравнений = 2*(n — 1) = 2n — 2.
Общая временная сложность в худшем случае = (2n — 2) * O (1) = O (n). Какой будет счет сравнения в лучшем случае? Думать! Мы используем постоянное дополнительное пространство, поэтому сложность пространства = O (1).
Использование подхода «разделяй и властвуй»
Можем ли мы мыслить рекурсивно, чтобы решить эту проблему? Вот идея разделяй и властвуй, похожая на алгоритм сортировки слиянием.
- Разделить. Разделить массив на две половины.
- Покорение:рекурсивный поиск максимума и минимума обеих половин.
- Объединить. Сравните максимум обеих половин, чтобы получить общий максимум, и сравните минимум обеих половин, чтобы получить общий минимум.
Шаги алгоритма
Предположим, что вызов функции minMax(X[], l, r) возвращает максимум и минимум массива, где l и r — левая и правая конечные точки.
- Разделите массив, вычислив средний индекс, т.е. mid = l + (r — l)/2
- Рекурсивно найдите максимум и минимум левой части, вызвав одну и ту же функцию, например leftMinMax[2] = minMax(X, l, mid)
- Рекурсивно найдите максимум и минимум правой части, вызвав одну и ту же функцию, например rightMinMax[2] = minMax(X, mid + 1, r)
- Наконец, получите общий максимум и минимум, сравнив минимум и максимум обеих половин.
if (leftMinMax[0] > rightMinMax[0]) max = lminMax[0] else max = rightMinMax[0] if (leftMinMax[1] < rightMinMax[1]) min = leftMinMax[1] else min = rightMinMax[1]
- Сохраните максимум и минимум в выводе [2] и верните его.
Базовый вариант 1.Если размер массива уменьшается до 1 во время рекурсии, верните этот единственный элемент как максимальный и минимальный.
Базовый вариант 2. Если размер массива уменьшается до 2 во время рекурсии, сравниваются оба элемента и возвращаются максимум и минимум.
Псевдокод алгоритма
Алгоритм анализа
Предположим, что временная сложность входного размера n равна T(n). Итак, нам нужно определить рекуррентное соотношение для функции временной сложности T(n).
Мы рекурсивно решаем две подзадачи размера n/2 и делаем два сравнения, чтобы получить общий максимум и минимум. Таким образом, рекуррентное соотношение временной сложности: T(n) = 2 T(n/2) + 2, где T(2) = 1 и T(1) = 0.
Мы можем решить это рекуррентное соотношение, используя метод рекурсивного дерева и основную теорему. Для лучшего анализа предположим, что n является степенью числа 2.
Здесь подзадачи будут разделены поровну и завершатся в базовом случае размера ввода 2. Другими словами, рекурсия остановится, когда n/(2^i) = 2 => n = 2^(i+1) ……. (1).
Таким образом, общее количество операций сравнения в приведенном выше дереве рекурсии = сумма количества сравнений на каждом уровне = (2 + 4 + 8 + 2 ^ i ) + 2 ^ i = 2 (2 ^ i - 1) + 2 ^ i = 2 ^(i + 1) + 2^i — 2 = n + n/2–2 = 3n/2–2. Примечание. Если n не является степенью числа 2, то сравнений будет больше, чем 3n/2 -2.
Таким образом, временная сложность = (3n/2–2) * O(1) = O(n). Пространственная сложность равна размеру стека вызовов рекурсии, который равен высоте дерева рекурсии, т.е. O(logn). Примечание. Как мы видим, временная сложность составляет O (n), но мы решаем проблему, используя меньшее количество сравнений (в худшем случае).
Эффективный подход: увеличение цикла на 2
Идея алгоритма
В подходе грубой силы мы будем делать два сравнения для каждого элемента в худшем случае. Можем ли мы оптимизировать это, чтобы решить проблему, используя меньшее количество сравнений? Давай подумаем!!
Идея состоит в том, чтобы запустить один цикл, выбрать значения парами и отслеживать минимум и максимум. Предположим, мы обновили максимум и минимум до (i — 1)го индекса и сохранили их в переменных max и min. На следующей итерации мы рассматриваем пару значений с i-м и (i + 1)-м индексами и пытаемся обновить max и min до (i + 1)-го индекса.
Если X[i] ‹ X[i + 1], то X[i] будет кандидатом на минимум, а X[i + 1] будет кандидатом на максимум. Итак, мы сравниваем X[i] с min и X[i + 1] с max и обновляем обе переменные.
if (X[i] < min), we update min = X[i] if (X[i + 1] > max), we update max = X[i + 1]
Если X[i] > X[i + 1], то X[i + 1] будет кандидатом на минимум, а X[i] будет кандидатом на максимум. Итак, мы сравниваем X[i + 1] с min и X[i] с max и обновляем обе переменные.
if (X[i] > max), we update max = X[i] if (X[i + 1] < min), we update min = X[i + 1]
Здесь мы сделаем 3 сравнения в обоих сценариях, чтобы обновить максимум и минимум пары элементов. Таким образом, эта идея сэкономит одно сравнение по сравнению с подходом грубой силы, когда мы делаем 4 сравнения для двух элементов в худшем случае.
Шаги алгоритма
- Объявите переменные max и min для хранения максимума и минимума.
- Мы собираем элементы парами. Поэтому, если размер массива нечетный, инициализируйте min и max с помощью X[0] и переменную цикла i с 1. В противном случае сравните X[0] и X[1], инициализируйте min с меньшим значением, max с большим значением и переменной цикла я с 2.
Теперь запустите цикл до конца и обработайте элементы массива парами. На основе сравнения X[i] и X[i + 1]:
- Сравните большее из X[i] и X[i + 1] с максимальным значением и обновите максимальное значение.
- Сравните меньшее из X[i] и X[i + 1] с минимальным значением и обновите минимальное значение.
К концу цикла max и min сохранят максимум и минимум массива. Итак, мы берем массив output[2], сохраняем max на выходе[0], min на выходе[1] и возвращаем его.
Псевдокод алгоритма
Алгоритм анализа
Мы делаем три сравнения для каждой пары элементов как в лучшем, так и в худшем случае. Таким образом, общее количество операций сравнения =
- 3 * (n — 1)/2, если n нечетно.
- 1 + 3*(n — 2)/2 = 3n/2–2, если n четно.
Как мы видим, временная сложность равна O(n), но общее количество сравнений меньше, чем количество сравнений в подходе грубой силы.
Возможные дополнительные вопросы интервьюера
- Можете ли вы назвать другой сценарий, в котором мы решаем проблемы, увеличивая цикл на 2 или более?
- Каковы лучшие и худшие случаи во втором подходе? В какой ситуации количество подсчетов сравнения при подходе 2 равно количеству подсчетов сравнения при подходе 3?
- Как мы можем проанализировать временную сложность второго подхода, используя основную теорему или метод подстановки рекурсивного анализа?
- Почему пространственная сложность O(logn) во втором подходе?
- Какова будет временная сложность, если мы рассмотрим только базовый случай размера массива 1? Можем ли мы решить эту проблему, используя какой-то другой подход?
Похожие проблемы с кодированием для изучения
- Сортировка массива в осциллограмме
- Найти N повторяющихся элементов в массиве размером 2N
- Разделяй и властвуй идея максимальной суммы подмассива
- Разделяй и властвуй, чтобы найти элемент большинства
- Разделяй и властвуй, чтобы найти максимальную разницу в массиве
- Удалить дубликаты из отсортированного массива
- Действительная гора в массиве
- Переместить нули в конец
- Количество зданий, обращенных к солнцу
- Сортировка массива 0, 1 и 2
Для получения дополнительной информации изучите наш бесплатный Курс DSA и Блоги интервью по программированию.
Если у вас есть какие-либо вопросы/сомнения/отзывы, напишите нам по адресу [email protected]. Наслаждайтесь обучением, наслаждайтесь алгоритмами!
Первоначально опубликовано наhttps://www.enjoyalgorithms.com/blog/find-the-minimum-and-maximum-value-in-an-array/