词典最小排列，使得所有相邻的字母都是不同的 [英] Lexicographic minimum permutation such that all adjacent letters are distinct

问题描述

这是一项额外的学校任务，我们还没有收到任何教学，我不是在寻找完整的代码，但是一些开始的技巧会很酷.回家后会发布到目前为止我在 Java 中所做的事情，但这是我已经完成的事情.

It's a bonus school task for which we didn't receive any teaching yet and I'm not looking for a complete code, but some tips to get going would be pretty cool. Going to post what I've done so far in Java when I get home, but here's something I've done already.

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

So, we have to do a sorting algorithm, which for example sorts "AAABBB" to the ABABAB. Max input size is 10^6, and it all has to happen under 1 second. If there's more than one answer, the first one in alphabetical order is the right one. I started to test different algorithms to even sort them without that alphabetical order requirement in mind, just to see how the things work out.

第一个版本:

将 ascii 代码保存到 Integer 数组，其中 index 是 ascii 代码，值是该字符在 char 数组中出现的数量.然后我选择了 2 个最高的数字，并开始将它们一个接一个地发送到新的字符数组，直到某个数字更高，然后我交换到它.效果很好，但当然顺序不对.

Save the ascii codes to the Integer array where index is the ascii code, and the value is amount which that character occurs in the char array. Then I picked 2 highest numbers, and started to spam them to the new character array after each other, until some number was higher, and I swapped to it. It worked well, but of course the order wasn't right.

第二个版本:

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

Followed the same idea, but stopped picking the most occurring number and just picked the indexes in the order they were in my array. Works well until the input is something like CBAYYY. Algorithm sorts it to the ABCYYY instead of AYBYCY. Of course I could try to find some free spots for those Y's, but at that point it starts to take too long.

推荐答案

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

An interesting problem, with an interesting tweak. Yes, this is a permutation or rearranging rather than a sort. No, the quoted question is not a duplicate.

算法.

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

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

Some care required to avoid off-by-one errors (odd vs even number of input characters). Otherwise, just writing the code and getting it to work right is the challenge.

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

Note that there is one special case, where the number of characters is odd and the frequency of one character starts at (half plus 1). In this case you need to start with step 4 in the algorithm, outputting all one character alternating with each of the others in turn.

另请注意，如果一个字符占输入的一半以上，则在这种特殊情况下将其分开，则无法解决.这种情况可以通过检查频率提前检测到，或者在执行过程中当尾部包含所有一个字符时检测到.检测这种情况不是规范的一部分.

Note also that if one character comprises more than half the input then apart for this special case, no solution is possible. This situation may be detected in advance by inspecting the frequencies, or during execution when the tail consists of all one character. Detecting this case was not part of the spec.

由于不需要排序，因此复杂度为 O(n).每个字符被检查两次:一次是在计数时，一次是在将其添加到输出中时.其他一切都摊销了.

Since no sort is required the complexity is O(n). Each character is examined twice: once when it is counted and once when it is added to the output. Everything else is amortised.

这篇关于词典最小排列，使得所有相邻的字母都是不同的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！