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

Как мы можем сделать это наиболее эффективно? Учитывая список с повторяющимися элементами, задача состоит в том, чтобы переупорядочить элементы в списке, чтобы не было двух соседних элементов.

Input: [1,1,1,2,3] Output: [1,2,1,3,1] Input: [1,1,1,2,2] Output: [1,2,1,2,1] Input: [1,1] Output: Not Possible Input: [1,1,1,1,2,3] Output: Not Possible 

Редактировать: Алгоритм вообще тоже! Это не должно быть Python.

Я плохо разбираюсь в 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.