[LeetCode]Reorganize String

这道题和Wiggle Sort II和Rearrange String K Distance Apart都很像。两者的方法也都可以借鉴过来。首先如果可以确定的是，如果一个char出现的次数大于(n + 1) / 2是无论如何都没法做到的。那么我们就从0开始，从频率最高的数开始每隔两位填偶数位就行了，超过界限就从1开始填奇数位。注意处理长度n为奇数，最大频率为(n + 1) / 2的情况即可。时间复杂地O(n * log n)，代码如下：


另一种方法，是仿照Rearrange String K Distance Apart的方法，用heap维护最大频率，每次取合法的最大频率的char即可。合法的必须是上一位没有取过的，我们可以维护这个信息，也可以每次pop优先队列的前两个来避免这个问题。时间复杂度相同，代码如下：