Я сталкивался с этим вопросом в недавнем интервью:
Учитывая массив длины N, нам нужно найти минимальную стоимость для преобразования этого массива в красивый массив.
Прекрасныймассив - это массив, который имеет вид A1^f1 A2^f2 A3^f3 ..., где все Ai различны, а fi - число раз, когда это происходит. т. е. {3^2 4^3 1^2} = {3,3,4,4,4,1,1}
Единственная разрешенная операция - выбрать любое число в массиве и заменить все его вхождения на новое число. Стоимость операции - частота преобразованного целого числа. то есть {1,3,1,3,1} => {1,1,1,1,1}. Здесь все 3 заменены на 1, а стоимость операции равна частоте 3 = 2.
Ограничения:
1 <= N <= 100000
1 <= Ai <= 200000
например,
A = {1,1,2,3,2,3} => {1,1,2,2,2,2}. Total cost = 2 (3 changed to 2)
A = {2,2,2,2,4}. Total cost = 0 (already beautiful array)
Я пробовал гдеЯ сохранил частоту всех элементов до каждого индекса в массиве. Затем, подбирая пару крайних концов вхождения каждого числа, я добавил частоту всех элементов, не встречающихся между этими двумя концами. Но, как и ожидалось, это не было оптимальным решением. Какой оптимальный подход мы можем применить для этой проблемы?