Поиск в массиве индексы и равенства элемент


Я задал этот вопрос из интервью он-лайн кодирвоание и мне предоставили мое решение, которое проходит все тесты. Я хотел увидеть, если кто-то может посмотреть мой код.

Массив Индексы И Равенства Элемент

Дан отсортированный массив arr для отдельных чисел, написать функцию indexEqualsValueSearch, которая возвращает наименьший индекс I, для которого модуль arr[я] == я. Возвращает -1 если нет такого индекса. Анализировать время и пространство сложностях ваше решение и объяснить его правильность.

Примеры:

вход: Арр = выход [-8,0,2,5]: 2 # с Арр[2] == 2

вход: ОБР = [-1,0,3,6] выход: -1 # поскольку нет индекса в Арр удовлетворяет модуль arr[я] == я.

[вход] массива.число Арр [выход]: interger

Я думаю, что вы можете найти этот вопрос по этой ссылке.

Моя реализация использует бинарный поиск, который дает мне \$о(Лог(Н))\$ время, сложность, и сложность пространства \$О(1)\$ в моем решении.

def index_equals_value_search(arr):
    left = 0
    right = len(arr) - 1

    ind = 0
    last = -1
    while left < right:
        ind = (left + right) // 2
        if arr[ind] - ind < 0:
            left = ind + 1
        elif arr[ind] == ind:
            right = ind - 1
            last = ind
        else:
            right = ind - 1
    if arr[left] == left:
        return left
    return last

Тестовый случай:

Passed 6 Test cases:
Test Cases #1
Input: [0],Expected: 0,Actual: 0
Test Case #2
Input: [0,3],Expected: 0,Actual: 0
Test Case #3
Input: [-8,0,1,3,5],Expected: 3,Actual: 3
Test Case #4
Input: [-5,0,2,3,10,29],Expected: 2,Actual: 2
Test Case #5
Input: [-5,0,3,4,10,18,27],Expected: -1,Actual: -1
Test Case #6
Input: [-6,-5,-4,-1,1,3,5,7],Expected: 7,Actual: 7


Комментарии
1 ответ

Я думаю, что вы сделали правильный выбор в бинарных искать эту проблему. Я согласен, что с точки зрения асимптотической сложности это \$ о (лог(н)) \ в раз$ и $ \ о(1) \$ в пространстве.

Линии ind = 0 является ненужным, поскольку оно будет сброшено 3 строк, прежде чем он когда-либо использовал.

Реализация, похоже, в целом твердая и у вас есть пограничные случаи покрываются. Я думаю, что можно упростить, что в прошлом if arr[left] == left: проверить путем изменения цикла условие while left <= right:. Это означает, что компьютер работает пару лишних строк кода идет через петлю в последний раз вместо вас писать (и компьютер разбор) пару лишних строк кода проверки пограничном случае. Я бы, наверное, за единообразие кода, но там не так много в нем.

Я думаю, что если я пишу, что внутренний блок испытания я бы сделал это немного по-другому. Я бы сначала проверить на равенство и установить последний в случае совпадения, а потом и самостоятельно (т. е. не в elif) проверить, в какую сторону искать. Это просто делает его легче увидеть, что вы делаете, в плане записи работает лучше и продолжить поиск. То, что выглядит немного как это

    if arr[ind] == ind:
last = ind # found a satisfying index. Record it

if arr[ind] >= ind:
right = ind - 1 # Navigate left for smallest satisfying index
else:
left = ind + 1 # Navigate right for smallest satisfying index

Вы могли бы сделать пару замечаний, чтобы помочь сделать его понятнее, что происходит. В частности, я был бы признателен за комментарий, объясняющий, что ваш алгоритм делает на высоком уровне, и где он отличается от того, что я мог бы ожидать. То есть, например, что он использует двоичный поиск, и что он не сразу вернуться на поиске решения, потому что он должен самой низкой удовлетворяющее число.
Также на ясности кода, я найти имя переменной last запутанным. Что это последняя? Это может быть либо выгоду от комментария, сказав, что это лучший индекс удовлетворения найден до сих пор, или переименование на этот счет.

if arr[ind] - ind < 0: это немного странно и неоправданно сложный способ написания if arr[ind] < ind:. В Python, как это обычно эквивалентны, так как Python, как правило, использует целые числа произвольной точности, но в некоторых случаях это использовании стиля с фиксированной длиной целочисленное представление, что на самом деле может дать неправильный ответ из-за целочисленное переполнение.

На очень педантичный, обратите внимание, этот ответ является потенциально ошибочные половину времени, потому что он игнорирует отрицательные индексы. Python позволяет индексирования a[-x] вернуться на х-й вход с торца. Если ваш входной массив a=[-7, -2, 5] тогда a[-2]==-2 а -2-Это самый низкий показатель. Я думаю, что это авария на часть вопроса сеттер, и я уверен, что они не имеют его в виду, потому что они просили не возвращать код, который в противном случае был бы юридическое кода возврата. Вероятно, в случае "уточнения требований" в интервью или ситуацию развития, а не "изменить код", но стоит иметь в виду.

2
ответ дан 22 апреля 2018 в 07:04 Источник Поделиться