字典最小排列使得所有相邻字母都是不同的
这是一个额外的学校任务，我们还没有接受任何教学，我不是在寻找完整的代码，但是一些提示将会非常酷。 我回到家时会发布到目前为止我用Java做的事情，但这里已经有了我已经做过的事情。
因此，我们必须进行排序算法，例如将“AAABBB”排序到ABABAB。 最大输入大小为10 ^ 6，所有这些都必须在1秒内完成。 如果有多个答案，则按字母顺序排列的第一个答案是正确答案。 我开始测试不同的算法，甚至在没有字母顺序要求的情况下对它们进行排序，只是为了看看事情是如何运作的。
第一版：
将ascii代码保存到Integer数组中，其中index是ascii代码，值是char数组中该字符出现的数量。 然后我选择了2个最高的数字，并开始将它们互相垃圾邮件发送到新的字符数组，直到某个数字更高，然后我换了它。 它运作良好，但当然订单不对。
第二版：
遵循相同的想法，但停止选择最常出现的数字，并按照它们在我的数组中的顺序选择索引。 运作良好，直到输入像CBAYYY。 算法将其分类为ABCYYY而不是AYBYCY。 当然，我可以尝试为那些Y找到一些免费的位置，但在那时它开始花费太长时间。
一个有趣的问题，有一个有趣的调整。 是的，这是一种排列或重新排列而不是一种排列。 不，引用的问题不重复。
算法。
- 计算字符频率。
- 从字母顺序的两个最低输出交替字符。
- 每个人都筋疲力尽，转到下一个。
- 在某些时候，最高频率的char将恰好是其余字符的一半。 此时切换到按字母顺序依次与剩余的其他字符交替输出所有该字符。
需要注意避免一个一个错误（奇数与偶数个输入字符）。 否则，只需编写代码并使其正常工作就是挑战。
请注意，有一种特殊情况，其中字符数为奇数，一个字符的频率从（半加1）开始。 在这种情况下，您需要从算法中的步骤4开始，依次输出所有一个字符与其他字符交替。
另请注意，如果一个字符包含输入的一半以上，那么对于这种特殊情况，则无法解决问题。 可以通过检查频率或在尾部由所有一个字符组成的执行期间预先检测这种情况。 检测此案例不属于规范。
由于不需要排序，因此复杂度为O（n）。 每个字符都要检查两次：一次计数，一次加入输出。 其他一切都是摊销的。
我的想法如下。 通过正确的实现，它几乎是线性的。
首先建立一个function来检查解决方案是否可行。 它应该非常快。 像最常见的字母> 1/2所有字母的东西，如果它可以是第一个，则考虑到它们。
然后，在仍有字母的情况下，按照字母顺序排列第一个与之前不同的字母，并进一步解决问题。
正确的算法如下：
- 构建输入字符串中字符的直方图。
- 将CharacterOccurrences放在PriorityQueue / TreeSet中，它们按照最高出现次数，最低字母顺序排序
- 有一个CharacterOccurrence类型的辅助变量
-
PQ不为空时循环
- 拿起PQ的头并保留它
- 将头部的字符添加到输出中
- 如果设置了辅助变量=>重新添加到PQ
- 将保留的头部存储在辅助变量中，少发生1次，除非事件最终为0（然后取消设置）
-
如果输出的大小==输入的大小，则有可能并且您有答案。 否则这是不可能的。
复杂度为O（N * log（N））
制作字符频率的双向表： character->count和count->character 。 记录一个optional ，它存储最后一个字符（或者没有任何一个字符）。 存储总字符数。
如果（字符总数-1）<2 *（最高计数字符数），请使用最高计数字符计数字符。 （否则就没有解决方案）。 如果它是最后一个字符输出则失败。
否则，按字母顺序使用最早的字符，而不是最后一个字符输出。
记录最后一个字符输出，减少总字符数和使用字符数。
循环，而我们仍然有字符。
虽然这个问题并不是一个重复的问题，但我的答案部分给出了用尽可能少的相邻相等字母枚举所有排列的算法，可以适应只返回最小值，因为它的最优性certificate要求每个递归调用产生至少一个排列。 测试代码之外的更改范围是按排序顺序尝试键，并在找到第一个匹配后中断。 下面代码的运行时间是多项式（如果我更好的数据结构，则为O（n）），因为与其祖先不同，它不会枚举所有可能性。
david.pfx的回答暗示了这一逻辑：贪婪地采用不能消除所有可能性的字母，但正如他所指出的那样，细节是微妙的。
from collections import Counter from itertools import permutations from operator import itemgetter from random import randrange def get_mode(count): return max(count.items(), key=itemgetter(1))[0] def enum2(prefix, x, count, total, mode): prefix.append(x) count_x = count[x] if count_x == 1: del count[x] else: count[x] = count_x - 1 yield from enum1(prefix, count, total - 1, mode) count[x] = count_x del prefix[-1] def enum1(prefix, count, total, mode): if total == 0: yield tuple(prefix) return if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]: yield from enum2(prefix, mode, count, total, mode) else: defect_okay = not prefix or count[prefix[-1]] * 2 > total mode = get_mode(count) for x in sorted(count.keys()): if defect_okay or [x] != prefix[-1:]: yield from enum2(prefix, x, count, total, mode) break def enum(seq): count = Counter(seq) if count: yield from enum1([], count, sum(count.values()), get_mode(count)) else: yield () def defects(lst): return sum(lst[i - 1] == lst[i] for i in range(1, len(lst))) def test(lst): perms = set(permutations(lst)) opt = min(map(defects, perms)) slow = min(perm for perm in perms if defects(perm) == opt) fast = list(enum(lst)) assert len(fast) == 1 fast = min(fast) print(lst, fast, slow) assert slow == fast for r in range(10000): test([randrange(3) for i in range(randrange(6))])
首先计算数组中每个字母的数量：
例如，你有3 – A，2 – B，1 – C，4 – Y，1 – Z.
1）然后你把每次最低的一个（它是A），你可以把。
所以你从：
一个
然后你不能再放A了所以你把B放：
AB
然后：
ABABACYZ
如果你还有至少2种字符，这些工作。 但在这里你仍然会有3个Y.
2）要放置最后一个字符，你只需从你的第一个Y开始，然后在开头的方向上插入一个。（我不知道这些是用英语说的好方法）。
所以ABAYBYAYCYZ。
3）然后你把你的Y之间的后续顺序，所以YBYAYCY和你之间的字母Y：
BAC => ABC
你到了
ABAYAYBYCYZ
这应该是你的问题的解决方案。
要做所有这些，我认为LinkedList是最好的方法
我希望它有帮助:)