Проблема национального флага Маврикия
Я нашел решение для проблемы голландского национального флага уже.
Но на этот раз я хочу попробовать что-то более сложное: проблема с национальным флагом Маврикия - 4 цвета вместо 3. Есть ли предложения по эффективному алгоритму?
В основном, проблема с национальным флагом Маврикия фокусируется на том, как вы сможете отсортировать данный список пар на основе порядка цветов в Маврикий национальный флаг (красный, синий, желтый, зеленый). И числа должны быть отсортированы в порядке возрастания.
Пример ввода схемы программирования:
((R. 3) (G. 6) (Y. 1) (B. 2) (Y. 7) (G 3) (Р.1) (B. 8))
Выход:
((R. 1) (R. 3) (B. 2) (B. 8) (Y. 1) (Y 7) (G. 3) (G. 6))
1 ответ
Это похоже на проблему с национальным флагом Нидерландов, но у нас есть четыре цвета. По сути, применяется та же стратегия. Предположим, у нас есть (где ^ обозначает сканируемую точку).
RRRRBBB???????????YYYYGGGG
^
и мы сканируем
- красный цвет, затем мы меняем местами первый синий с текущим узлом
- СИНИЙ, мы ничего не делаем
- желтый, мы меняем местами с последним?
- Зеленый, мы меняем местами последний желтый с узлом последний ? Затем текущий узел с замененным?
Итак, нам нужно отслеживать или на один указатель больше, чем обычно.
Нам нужно отслеживать первый синий, первый?, Последний?, Последний Y
В общем, одна и та же стратегия работает для любого количества цветов, но требуется все большее количество замен.