Мне дали в интервью следующий вопрос, мне дали массив целых чисел, и мне нужно вернуть количество целых чисел в массиве, которых нет в индексе, который был бы, если бы массив был отсортирован.
Например, для массива [1,1,3,4,1] мне нужно вернуть 3, потому что последние три целых числа (3,4,1) не находятся в индексах, в которых они были бы, если бымассив был отсортирован, [1,1,1,3,4].А для [5,4,3,2,1] мне нужно вернуть 4, ([1,2,3,4,5]).
Я только придумал наивное решение, котороескопировать исходный массив, а затем отсортировать его и сравнить два массива, а затем подсчитать количество различных элементов в каждом индексе.Это занимает O (nlogn) время и O (n) пространство.
Мне кажется, что я что-то упускаю, и может быть лучшее решение.Есть ли лучшее решение?