java - 字典序最小排列，使得所有相邻字母都不同

Question

这是一项额外的学校任务，我们还没有收到任何教学，我也不是在寻找完整的代码，但一些开始的提示会很酷。我打算在回家后发布我到目前为止用 Java 完成的工作，但这里有一些我已经完成的工作。

因此，我们必须做一个排序算法，例如将“AAABBB”排序为 ABABAB。最大输入大小为 10^6，并且这一切都必须在 1 秒内发生。如果有多个答案，则按字母顺序排列的第一个答案是正确的。我开始测试不同的算法，甚至在不考虑字母顺序要求的情况下对它们进行排序，只是为了看看结果如何。

第一版:

将ascii码保存到Integer数组中，index为ascii码，value为该字符在char数组中出现的次数。然后我选择了 2 个最高的数字，并开始将它们一个接一个地发送到新的字符数组，直到某个数字更高，然后我换成它。它运行良好，但当然顺序不正确。

第二个版本:

遵循相同的想法，但停止选择出现次数最多的数字，而是按照它们在我的数组中的顺序选择索引。在输入类似于 CBAYYY 之前效果很好。算法将其排序为 ABCYYY 而不是 AYBYCY。当然，我可以尝试为那些 Y 找到一些空闲位置，但到那时它开始花费太长时间。

Answer 1

一个有趣的问题，有一个有趣的调整。是的，这是排列或重新排列，而不是排序。不，引用的问题不是重复的。

算法。

1. 计算字符频率。
2. 从字母顺序最低的两个字符交替输出。
3. 当每个都用完后，转到下一个。
4. 在某些时候，出现频率最高的字符恰好是其余字符的一半。那时切换到输出所有该字符，并按字母顺序依次与其他剩余字符交替输出。

需要注意避免差一错误(输入字符的奇数与偶数)。否则，仅仅编写代码并让它正常工作就是一个挑战。

---

请注意，有一种特殊情况，字符数为奇数且一个字符的出现频率从(二分之一加 1)开始。在这种情况下，您需要从算法的第 4 步开始，依次输出所有一个字符和其他字符。

另请注意，如果一个字符占输入的一半以上，则对于这种特殊情况，没有解决方案。这种情况可以通过检查频率提前检测到，或者在尾部全部由一个字符组成时在执行期间检测到。检测这种情况不是规范的一部分。

---

由于不需要排序，因此复杂度为 O(n)。每个字符被检查两次:一次是在计数时，一次是在将其添加到输出时。其他所有内容均已摊销。