java - 如何随机排列没有两个重复项的字符数组？

<分区>

我在面试中被问到这个问题:

How to shuffle a character array with no two duplicates next to each other?

我想出的算法是:

有一个 HashMap 字符，字符对的出现次数。通过这个找到重复元素与唯一元素的数量。
如果重复 > 唯一，则不能形成没有 2 的打乱数组彼此相邻的重复元素 (?)
如果唯一 >= 重复，则有 2 个堆栈 - 1 个包含唯一字符和一个包含重复字符的字符。构建以从唯一堆栈中弹出元素的方式生成数组首先，然后从重复堆栈中弹出一个元素。重复

例如:

[a,b,b,c] shuffled array with above algorithm - [a,b,c,b];

[b,b,b,c] unique < duplicate return error

但我很确定我使逻辑过于复杂了。有没有更简单、更简单的方法来做到这一点？

最佳答案

[正如评论中指出的那样，有一个测试用例失败了]
所以如果引用我的回答，请注意同样的问题我明白了，但如果你有 'a'->4、'b'->2 和 'c'->1，它似乎不起作用。因为第一步是“abc”，留下'a'->3 'b'->1。但有一个答案:“ababaca”。 – user3386109

案例 1:构建基本算法

使用 HashMap (键是字符，它的出现是值)来计算出现次数。这将为我们提供桶，如果我们有“cbaaba”，将提供 3 个桶，其中“c”的值为 1，“a”的值为 3，“b”的值为 2。
根据出现次数对桶进行排序，其中出现次数最多的元素排在最前面。所以现在我们有

'a' -> 3，'b' -> 2，'c' -> 1

结果数组将从以排序方式从 3 个桶中各取一个开始。

“abc”，现在我们的桶为 'a'->2，'b'-> 1 和 'c'->0

接下来我们再次尝试从已排序的桶中获取每个元素(忽略具有 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 中的相同方式继续进行，我们尝试构建结果

=>结果=“abcd”

'a'--> 3
'bc'--> 2
'd'--> 1

=>result = "abcdabcd"

'a'--> 2
'bc'--> 1
'd'--> 0

=>result = "abcdabcdabc"

'a'--> 1
'bc'--> 0
'd'--> 0

=>最终结果 = "abcdabcdabca"

关于java - 如何随机排列没有两个重复项的字符数组？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37040164/