Я видел этот вопрос на Reddit, и никаких положительных решений не было представлено, и я подумал, что здесь будет прекрасный вопрос. Это было в теме о вопросах интервью:
Напишите метод, который принимает массив int m и возвращает (True/False), если массив состоит из чисел n... n + m-1, все числа в этом диапазоне и только числа в этом диапазоне, Массив не может быть отсортирован. (Например, {2,3,4} вернет true. {1,3,1} вернет false, {1,2,4} вернет false.
Проблема, с которой я столкнулся, заключается в том, что мой интервьюер продолжал просить меня оптимизировать (быстрее O (n), меньше памяти и т.д.) до такой степени, что он утверждал, что вы можете сделать это за один проход массива, используя постоянный объем памяти. Никогда не приходило в голову, что один из них.
Наряду с вашими решениями укажите, считают ли они, что массив содержит уникальные элементы. Также укажите, будет ли ваше решение предполагать, что последовательность начинается с 1. (Я немного изменил вопрос, чтобы разрешить случаи, когда он идет 2, 3, 4...)
edit: Я считаю, что в пространстве не существует линейного по времени и константы в пространственном алгоритме, который обрабатывает дубликаты. Кто-нибудь может это подтвердить?
Повторяющаяся проблема сводится к тестированию, чтобы увидеть, содержит ли массив дубликаты в O (n) времени, O (1) пробел. Если это можно сделать, вы можете просто проверить сначала, и если нет дубликатов, выполните опубликованные алгоритмы. Итак, можете ли вы проверить наличие дубликатов в O (n) времени O (1) пробел?