Вступление:. Насколько я мог искать, этот вопрос еще не задавался в SO.
Это вопрос интервью.
Я даже не ищу программного кода, любой алгоритм/псевдокод будет работать.
Проблема: Задано целочисленным массивом int[] A
и его размером N
, найдите 2 не последующих (не могут быть смежными в массиве) элементы с минимальной суммой. Также ответ не должен содержать первый или последний элементы (индекс 0
и n-1
). Также решение должно быть в O(n)
сложности времени и пространства.
например. когда A = [5, 2, 4, 6, 3, 7]
ответ 5
, так как 2+3=5
.
Когда A = [1, 2, 3, 3, 2, 1]
ответ 4
, так как 2+2=4
и вы не можете выбрать любой из 1
, так как они находятся на концах массива.
Попытка: Сначала я думал, что один из числа в решении должен быть самым маленьким в массиве (кроме первого и последнего), но это было быстро опровергается встречным примером A = [4, 2, 1, 2, 4]
-> 4 (2+2)
Тогда я подумал, что если я найду наименьшие числа 2 (помимо первого и последнего) в массиве, то это будет два. Это, очевидно, быстро провалилось, потому что я не могу выбрать 2 соседних номера, и если мне нужно выбрать несмежные номера, это будет само определение вопроса:).
Наконец Я подумал, что я просто найду наименьшие числа 3 (помимо первого и последнего) в массиве, и решение должно быть два из тех, поскольку два из них не должны быть смежными друг с другом.
Этот также не удалось из-за A = [2, 2, 1, 2, 4, 2, 6]
-> 2+1=3
, который, похоже, работает, потому что я найду 2, 1, 2
, но если я нахожу 2, 1, 2
в индексах 1, 2, 3
, это не будет обязательно (если бы я нашел именно 2
в индексе 5
, но я не могу этого гарантировать).
Вопрос: Теперь я в тупике, может ли кто-нибудь придумать решение/идею, которая работает?