Имеется строка длиной до 10^5 символов A..Z. Задача состоит в том, чтобы переставить его так, чтобы ни один из символов не образовывал ряд. Для нескольких решений правильным является то, которое идет первым в алфавитном порядке. И это должно быть сделано в разумные сроки, конечно.
Итак, я попробовал два подхода, и один из них перестраивает правильно, но очень неэффективно, а другой, я думаю, нарушил логику.
Медленный подход.
- Сортировать массив символов
- Перестановка на месте, аналогичная сортировке вставками (поэтому она такая медленная)
Неправильный подход (не всегда дает первый ответ в алфавитном порядке)
- Сортировать
- Переместите элементы, начиная с конца, в другой массив, сохраняя инвариант
- Обратный
Я действительно застрял и не могу думать ни о чем другом здесь.
Примеры:
"HHABC" -> "ABHCH";
"CBAXXXX" -> "XAXBXCX";
"AAABBBCCCCCCCDDDDD" -> "ABABACBCDCDCDCDCDC";
Вот алгоритм решения модели в деталях. Я думаю, что мне не разрешено публиковать фактический код, поэтому он такой:
- Постройте гистограмму. Он может храниться в массиве целых чисел, где индексами являются ascii-коды, поэтому сопоставление не требуется.
- Build the new string:
- for each character go alphabetically, from A to Z
- если по гистограмме такого символа нет, переходим к следующему
- если предыдущий написанный символ был таким же, перейти к следующему (если это не первая итерация)
- написать первый найденный подходящий символ
- уменьшить число на гистограмме
- если есть (длина-i+2)/2 текущего символа (половина того, что осталось), выйти из этого цикла и перейти к следующему символу в строке.
Это намного короче и проще, чем тот беспорядок, который я написал в конце концов (хотя он работал нормально, и большое спасибо за помощь).
