Оставить в массиве k различных чисел
В университете дали задание, не могу придумать как решить: Дан массив длины n, нам при помощи двух действий (прибавление к наименьшему элементу массива единицы или вычитание из наибольшего элемента 1) надо сделать так, чтобы в массиве после всех действий осталось k различных чисел. То есть, из массива -1; -5; 7; 8; 2; 1; 10, надо получить -1; -1; 7; 7; 7; 2; 1. Может кто встречался с подобным, а то из идей была только сортировка, но я не понимаю, что делать с этим дальше...
Ответы (1 шт):
Хорошо, отсортировали по возрастанию.
Теперь используем метод двух указателей.
Левый индекс поставим на 0, правый тоже, и начнём двигать правый, пока в окне между двух указателей от L до R-1 не будет ровно k различных элементов.
Теперь посчитаем сумму значений справа RSum, и сколько нужно от значений справа отнять единиц, чтобы все правые элементы стали как R-1-ый, это начальное значение для
MinOnes = RSum - A[R-1]*(n-R)
Начинаем двигать левый указатель, пока количество различных элементов в окне не станет меньше k, при этом считая сумму, оставшуюся слева LSum.
Продолжим двигать правый, как и раньшe, уменьшая RSum. При остановке правого посчитаем необходимое количество единиц и сравним с MinOnes
Ones = (RSum - A[R-1]*(n-R)) + ((A[L]*(L-1) - LSum))
Повторяем продвижение окна, содержащего ровно k различных элементов, до конца.