如何洗牌一个没有两个重复的字符数组?

2022-01-10 00:00:00 algorithm arrays duplicates shuffle java

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

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 的 shuffled 数组相邻的重复元素 (?)
  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.但有一个答案:蕉麻".– user3386109

案例一:构建基本算法

  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

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

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

"abcab" 现在我们的桶状态变为:'a'-> 1 ，'b'-> 0 和 '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

=>结果 = "abcd"

=>result = "abcd"

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

=>结果 = "abcdabcd"

=>result = "abcdabcd"

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

=>结果 = "abcdabcdabc"

=>result = "abcdabcdabc"

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

=>最终结果 = "abcdabcdabca"

相关文章