如何打乱一个没有两个重复的字符数组? [英] How to shuffle a character array with no two duplicates next to each other?

问题描述

我在一次采访中被问到这个问题:

I was asked this question in an interview:

如何打乱一个没有两个重复的字符数组?

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

我想出的算法是:

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

1. have a HashMap of Character, count of occurrence of Character pairs. With this find the count of duplicate vs unique elements.
2. If duplicate > unique, cannot form a shuffled array with no 2 duplicate elements next to each other (?)
3. if unique >= duplicate, have 2 stacks - 1 containing unique characters and one containing duplicate characters. Construct the resulting array in such a way that pop an element from unique stack first and pop an element from duplicate stack next. Repeat

例如:

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

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

但我很确定我把逻辑过于复杂了.有没有更简单且万无一失的方法来做到这一点?

But I am pretty sure I am overcomplicating the logic. Is there an easier and fool proof way to do this?

推荐答案

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

案例 1:构建基本算法

1. 使用哈希图(键是字符，出现的次数是值)来计算出现的次数.这将为我们提供桶，就像我们有cbaaba"将提供 3 个桶，其中 'c' 值为 1，'a' 值为 3，'b' 值为 2.

1. use a hashmap (key being the character and its occurance being the value) to count the occurances. This will give us buckets like if we have "cbaaba" will give 3 buckets with 'c' with value 1, 'a' with value 3 and 'b' with value 2.

根据出现次数最多的元素对桶进行排序.所以现在我们有

Sort the buckets based on the occurances with element with most occurancr first. so now we have

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

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

1. 从最大出现次数桶中获取元素，将其在map中的计数减1并将其放入结果数组中.根据排序的出现桶对后续出现桶执行此操作.

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

result array will start with taking one each from 3 buckets in sorted fashion.

"abc" 现在我们的桶为 'a'->2 , 'b'-> 1 和 'c'-> 0

"abc" and now we have our buckets as 'a'->2 , 'b'-> 1 and 'c'-> 0

接下来我们再次尝试从已排序的桶中获取每个 elemet(忽略具有 0 个元素的桶)

next we again try to get elemet each from sorted buckets (ignoring the buckets with 0 elements)

"abcab" 现在我们的桶状态变成: 'a'-> 1 , 'b'-> 0 and 'c'-> 0

"abcab" now our buckets state become as : 'a'-> 1 , 'b'- > 0 and 'c'-> 0

接下来我们继续得到我们的结果

next as above we proceed to have our result as

=> "abcaba".

=> "abcaba".

情况 2:如果字符串类似于 "aaaabbbcccdd"

我们将有桶

'a'--> 4
'b'--> 3
'c'--> 3
'd'--> 2

这里我们有 b 和 c 的桶具有相同的大小.每当这种情况发生时，我们必须执行一个JoinBuckets操作，它将把'b'和'c'连接到一个桶中，'bc'将被视为一个单个元素.

Here we have bucket of b and c having same size. When ever such situation occurs we have to perform an operation of JoinBuckets, It will join 'b' and 'c' in single bucket and 'bc' will be considered as a single element.

现在我们的桶将是

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

现在以与情况 1 相同的方式继续进行，我们尝试构建结果

Now proceeding ahead in same manner as done in case 1, we try to build the result

=>result = "abcd"

=>result = "abcd"

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

=>result = "abcdabcd"

=>result = "abcdabcd"

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

=>result = "abcdabcdabc"

=>result = "abcdabcdabc"

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

=>最终结果 = "abcdabcdabca"

这篇关于如何打乱一个没有两个重复的字符数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！