Переупорядочить элементы в списке таким образом, чтобы ни один из двух соседних одинаковых

Я плохо разбираюсь в python, поэтому я пишу общий алгоритм здесь –

1. Создайте максимальную кучу , maxHeap которая хранит числа и их частоты <array element, frequency> . maxHeap будет сортироваться по частоте элемента.

2. Создайте временный ключ, который будет использоваться как предыдущий посещенный элемент (предыдущий элемент в результирующем массиве). Инициализируйте его как <item = -inf , freq = -1> .

3. Пока maxHeap не пуст

   • Поместите элемент и добавьте его в результат.
   • Уменьшить частоту всплывающего элемента на 1
   • Нажмите предыдущий элемент обратно в максимальную кучу, если это частота> 0
   • Сделайте текущий элемент как предыдущий элемент для следующей итерации.

4. Если длина результирующего массива и оригинала, для этого массива нет решения. Else возвращает результирующий массив.

редактировать

Те, кто задается вопросом, почему жадное решение, помещая текущий самый частый элемент в четные / нечетные позиции, пропуская одну позицию каждый раз, не будет работать, вы можете попробовать тестовый корпус [1 1 2 2 3 3] .

Пусть n – размер списка. Если какой-то элемент встречается по крайней мере (n + 2) / 2 (целочисленное деление), то, очевидно, нет решения (согласно принципу голубинки).

В противном случае мы всегда можем построить ответ. Мы можем сделать это следующим образом: давайте сначала записать все четные позиции, а затем все нечетные позиции (я использую индексы на основе 0). После этого давайте отсортировать элементы по их частоте (в порядке убывания) и заполнить позиции в порядке, описанном выше (примечание: элементы сортируются как пары (частота, элемент), так что одни и те же элементы группируются вместе. отсортировано только один раз в самом начале построения ответа).

Этот алгоритм может выполняться в линейном времени, если мы используем хеш-таблицу для подсчета элементов и сортировки по частоте с использованием сортировки count.