Сложность: Средняя, ​​Вопросы: 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? Можем ли мы решить эту проблему, используя какой-то другой подход?

Похожие проблемы с кодированием для изучения

Для получения дополнительной информации изучите наш бесплатный Курс DSA и Блоги интервью по программированию.

Если у вас есть какие-либо вопросы/сомнения/отзывы, напишите нам по адресу [email protected]. Наслаждайтесь обучением, наслаждайтесь алгоритмами!

Первоначально опубликовано наhttps://www.enjoyalgorithms.com/blog/find-the-minimum-and-maximum-value-in-an-array/