如何将没有两个重复的字符数组混合在一起？
我在接受采访时被问到这个问题：
如何将没有两个重复的字符数组混合在一起？
我想出的算法是：
- 有一个字符的
HashMap，字符对的出现次数。 通过此查找重复与唯一元素的计数。 - 如果duplicate> unique，则不能形成一个没有2个重复元素的混洗数组（？）
- 如果unique> = duplicate，则有2个堆栈 – 1个包含唯一字符，1个包含重复字符。 构造结果数组的方式是首先从唯一堆栈中弹出元素，然后从重复堆栈中弹出元素。 重复
例如：
[a,b,b,c] shuffled array with above algorithm - [a,b,c,b]; [b,b,b,c] unique < duplicate return error
但我很确定我的逻辑过于复杂。 有没有更容易和万无一失的方法来做到这一点？
案例1：构建基本算法
-
使用hashmap（键是字符，其出现是值）来计算出现次数。 这将给我们提供桶，就像我们有“cbaaba”将给3个桶’c’值1，’a’值3和’b’值2。
-
根据具有最多占优势的元素的出现对存储桶进行排序。 所以现在我们有
‘a’ – > 3，’b’ – > 2，’c’ – > 1
- 从max occurrence桶获取元素，在map中将其计数减少1并将其放入结果数组中。 根据已排序的出现桶，对此后续出现桶进行此操作。
结果数组将从排序方式从3个桶中取出一个开始。
“abc”现在我们把我们的桶称为’a’ – > 2，’b’ – > 1和’c’ – > 0
接下来我们再次尝试从排序桶中获取elemet（忽略带有0个元素的桶）
“abcab”现在我们的桶状态变为：’a’ – > 1，’b’ – > 0和’c’ – > 0
接下来我们继续将结果作为
>“abcaba”。
案例2：如果字符串像“aaaabbbcccdd”
我们将有桶作为
'a'--> 4 'b'--> 3 'c'--> 3 'd'--> 2
这里我们有一桶b和c具有相同的尺寸 。 当出现这种情况时，我们必须执行JoinBuckets的操作 ，它将在单个桶中加入’b’和’c’，并且’bc’将被视为单个元素。
现在我们的水桶将是
'a'--> 4 'bc'--> 3 'd'--> 2
现在以与案例1相同的方式继续前进，我们尝试构建结果
=> result =“abcd”
'a'--> 3 'bc'--> 2 'd'--> 1
=> result =“abcdabcd”
'a'--> 2 'bc'--> 1 'd'--> 0
=> result =“abcdabcdabc”
'a'--> 1 'bc'--> 0 'd'--> 0
=>最终结果=“abcdabcdabca”
我将从一个非常简单的算法开始：
public static void shuffleWithoutRepetition(char[] chars, Random rnd) { if (tooManySameCharacters(chars)) throw new IllegalArgumentException("Too many same characters"); do { shuffle(chars, rnd); // See java.util.Collections.shuffle } while (containsRepetition(chars)); }
这样，你有一些工作代码，当它变得太慢时，你可以在以后优化它。
- 这个算法对于改组
aaaaaaaaaaaaaaabbbbbbbbbbbbbbb非常慢，这很糟糕。 - 它以相同的概率生成每个可能的输出，这很好。
这基本上是一个排序问题。 它让我想起“巅峰发现”，但反过来说，你想在某种意义上“创造出独特物品的高峰”。
（2）的逻辑也有点偏。 如果我有N个重复的字母，我仍然可以与另一个字母的N-2没有相似的邻居：
'aaabb' -sort-> 'ababa'
这也certificate了寻找“独特”的问题，因为你很可能只有在数组中某处复制的字母。
伪：
foreach letter in string{ if next != self then happy, move to next if next == self, loop until spot != self and swap
可能有一种更好的分而治之的方法可以在更好的时间内通过它，但如果没有实际测试它我不确定。
SCALA代码。 复制并粘贴此程序并运行。
def rearrange(xs : List[Char]) : List[Char] ={ xs match { case Nil => Nil case x :: xs1 => xs1 match { case Nil => x :: Nil case y :: ys1 => if (x == y) { (x :: rearrange(ys1)) :+ y } else x :: y :: rearrange(ys1) } } } rearrange: (xs: List[Char])List[Char] rearrange("hello".toList)