Реализация на Python
На эту проблему отвечает Geeksforgeeks (здесь) и еще одна статья на Medium (здесь). Однако первое слишком короткое (осталось много деталей), а второе слишком длинное (включено слишком много деталей). Моя задача здесь состоит в том, чтобы сделать объяснение как можно более лаконичным, но при этом более познавательным.
Перейдем к проблеме.
Глупое решение: грубая сила
Это занимает экспоненциальное время и, вероятно, никогда не вернет результат для больших массивов. Кроме того, ни один интервьюер не принимает такой ответ; Итак, давайте представим, что этого решения не существует.
Лучшее решение:
В этом вопросе есть два ключевых факта, которые позволяют нам решить его за O(n)
время.
- Массив отсортирован. В противном случае вы не сможете решить ее менее чем за
O(n*log(n))
раз. - Начиная с начала массива, первое значение больше (сумма всех предыдущих значений + 1) - это то место, где у нас будет пробел. Окончательный ответ (сумма всех предыдущих значений + 1).
Но вы можете задаться вопросом, в чем магия первого значения в массиве больше (сумма всех предыдущих значений + 1)? Почему значения, меньшие или равные (сумма всех предыдущих значений + 1), являются допустимыми, и мы проходим мимо этих значений?
В порядке. В приведенном выше алгоритме result-1
- это в основном значение максимально возможного целого числа, которое может быть представлено. Другими словами, могут быть представлены все положительные целые числа от 1
до result-1
, т. Е. 1, 2, 3, …, result -1
Для каждого значения массива, если значение меньше или равно result
, тогда могут быть представлены все положительные целые числа от 1
до result - 1 + array value
, а result + array value
будет наименьшим значением, которое не может быть представлено.
Но если значение массива больше, чем result
, тогда будет по крайней мере одно положительное целое число от 1 до result + array value
, которое не может быть представлено.
Давайте объясним все эти шаги на примере, предполагая, что arr = [1, 1, 2, 4,6]. Ниже представлена пошаговая иллюстрация алгоритма.
Для индекса 3 значение массива равно 4
, что меньше result = 5
. Итак, result
переходит на result + 4 = 9
. Почему? потому что когда result = 5
, это означает, что мы можем представлять значения 1, 2, 3, and 4
. Добавление 4
в сгиб позволяет нам представить 1+4, 2+4, 3+4, and 4+4
. Как видите, максимально возможное значение становится 8
, и поэтому наименьшее значение, которое не может быть представлено, то есть result
, становится 9
.
Для индекса 4 значение массива - 11
, что больше, чем result = 9
. По тому же аргументу, если мы продолжим и включим 9
, мы можем представить 12, 13, 14, …, 19
. Как вы ясно видите, у нас есть пробел для целых чисел 10
и 11
, и он не принимается. Вот почему мы должны разорвать цикл и произнести result = 9
как наименьшее значение, которое не может быть представлено как сумма любого подмножества данного массива.
Реализация на Python:
def findSmallest(arr, n): result = 1 for i in range (0, n ): if arr[i] <= result: result = result + arr[i] else: break return result # Driver Code if __name__ == "__main__": arr = [1, 1, 2, 4, 11] n = len(arr) print(findSmallest(arr, n))
Если вы нашли эту статью полезной, поделитесь ею со своими друзьями и коллегами. Если у вас есть другие вопросы, вы можете найти меня в Linkedin или написать мне на почту [email protected].