Найти «Лучший» элемент из данного списка

Question

Мне недавно задали этот вопрос в одном из моих телефонных интервью.

"Есть список элементов. И вы должны найти элемент" best"из списка. Элементы сравнимы друг с другом, но сравнение не транзитивно . Например. если A> B и B> C, то значение A НЕ должно быть больше C.

Вы должны вернуть лучший элемент в качестве ответа, который лучше, чем любой другой элемент в списке. Возможно, такого элемента нет. В этом случае верните ноль. "

Мое решение:

Попытка 1:

Простое O (n ^ 2) решение. Сравнение каждого элемента с каждым другим элементом.

Интервьюер не был удовлетворен.

Попытка 2:

Начните сравнивать первый элемент со вторым элементом и далее. Для любого элемента 'E', если A> E, пометьте E (возможно, используя другой массив / список / и т. Д.) И не рассматривайте E для дальнейшего сравнения. Это потому, что есть по крайней мере 1 элемент, который лучше, чем E, поэтому E определенно не ответ.

Сложность все еще O (n ^ 2) с некоторым улучшением по сравнению с предыдущей попыткой.

Он все еще не был удовлетворен. Может кто-нибудь придумать какое-нибудь лучшее решение?

Answer 1

Конечно.У вас есть N элементов.Сравните первые два.Один из них «хуже» другого.Откажитесь от этого.Сравните «лучшее» из двух со следующим элементом.Продолжайте этот первый проход по списку, пока не останется только один элемент.Этот шаг O (N).

Один элемент, который пережил первый проход, теперь нужно сравнивать с каждым элементом из исходного списка, за исключением тех, с которыми он уже сравнивался.Если он «проигрывает» хотя бы один раз, вы возвращаете, что нет «лучшего» элемента.Если он «выигрывает» при каждом сравнении на этом шаге, вы возвращаете этот элемент.Этот шаг также O (N).

Этот алгоритм O (N + N) = O (N) в худшем случае и O (N + 0) == O (N) в лучшем случае,Далее мы можем доказать, что это наилучшая возможная сложность, потому что проверка решения также является O (N), и не может быть менее сложным, чтобы получить решение, чем проверить его.