Алгоритмы кодирования: Вращение массива | Кодементор

Проблема:

Отсортированный массив был повернут таким образом, что элементы могут располагаться в порядке 3 4 5 6 7 1 2. Как найти минимальный элемент? Вы можете предположить, что массив имеет уникальные элементы.

Решение:

Проанализируйте проблему, чтобы выбрать подход:
Давайте сначала посмотрим на информацию, которая у нас уже есть из самого определения проблемы. У нас есть две вещи:

  1. У нас есть отсортированный массив.
  2. Он повернут.
    Теперь давайте подумаем о возможностях понять, есть ли какие-либо присущие нашей проблеме сложности. Нам дано, что это отсортированный массив. Сортировка может происходить в порядке возрастания или убывания. Изменился бы наш подход к решению задачи, если бы порядок был изменен? Да и нет. Зависит от того, откуда мы смотрим (если вы чувствуете себя совершенно сбитым с толку этим утверждением, дождитесь объяснения в конце раздела «Расширение границ алгоритма»). А пока давайте просто предположим, что мы ответили «да» на этот вопрос (любой нормальный человек ответил бы). Если массив находится в порядке возрастания, мы ожидаем, что входные значения будут увеличиваться, а затем внезапно найдем меньшее значение. Для упорядоченного по убыванию массива было бы наоборот. Поэтому нам нужно решить, что мы ожидаем на входе. Поскольку образец примера в задаче находится в порядке возрастания, давайте предположим, что это правда, и просто вспомним, что наше решение предполагает, что отсортированный массив находится в порядке возрастания. И что на данный момент мы понятия не имеем, как мы подходим к проблеме, если мы не знали об этом. Итак, каков вывод в этом обсуждении? Когда кажется, что у вас нет всей информации для разработки подхода, вы делаете предположение.
    Предположение: входной массив отсортирован в порядке возрастания.

Теперь поговорим о ротации. Каковы возможности? Вращение может быть по часовой стрелке или против часовой стрелки. Давайте посмотрим, повлияет ли вращение массива по часовой стрелке против часовой стрелки на наш подход к проблеме. Начнем с того же набора нет: 1 2 3 4 5 6 7
Поворот по часовой стрелке на 2 нет: 6 7 1 2 3 4 5
Поворот против часовой стрелки на 2 секунды: 3 4 5 6 7 1 2
В обоих случаях мы видим, что возникновение странности — меньшее число (1), внезапно появляющееся после большего числа (7), происходит одинаково. Тогда на самом деле не имеет значения, вращали ли мы массив так или иначе. Следовательно, теперь мы знаем, что вращение не повлияет на результат и, следовательно, на наш подход к решению проблемы. Так что второе свойство вращения не влияет на наш подход к решению задачи.

Выберите подход (алгоритм):

Теперь, когда мы понимаем проблему, мы переходим к тому, как выбрать алгоритм для ее решения (если слово «алгоритм» пугает вас, просто подумайте о нем как о рецепте вкусного блюда — в основном «как» это сделать, но также «когда» и «где» — например, как вы жарите семена, когда кладете сахар и где его нагреваете (микроволновая печь).

Алгоритм будет ожидать ввода количества цифр в порядке возрастания, повернутого до некоторой точки. Итак, в основном, что мы можем сделать, это начать читать входные целые числа и проверить, находятся ли они в порядке возрастания. Как мы это делаем? Просто продолжайте проверять, меньше ли текущий номер следующего номера. В тот момент, когда мы обнаруживаем, что текущее «нет» больше, чем следующее «нет», мы достигли своей цели.

Код для него (сделайте его питоническим):

def find_min_element(L):
    """This method finds the min element in a sorted list/array that has been
    rotated.
    """
    for i,element in enumerate(L):
        if (i+1<len(L)):#making sure index not out of range
            if L[i+1]<element:
                return L[i+1]
    return None

if __name__=="__main__":
    L=map(int, raw_input('Input noes(sorted list, rotated, separated by space): ').split())
    print "Input List:",L

    minval=find_min_element(L)
    if minval is None:
        print "Array is not rotated. No element found"
    else:
        print "Rotated array. Min element:%d"%minval
ps: check if there is a better way in python to access next element?

Проверь это:

import unittest
from minlist import *

class TestRotatedArray(unittest.TestCase):

  def test_sorted_input_rotn(self):
      self.assertEqual(find_min_element([1,2,3,4,0]), 0)

  def test_sorted_input_no_rotn(self):
      self.assertEqual(find_min_element([1,2,3,4]), None)

if __name__ == '__main__':
    unittest.main()
    
>>python unitestminlist.py
Ran 2 tests in 0.000s

OK

Похожие записи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *