如何随机播放一个没有两个副本的字符数组？ [英] How to shuffle a character array with no two duplicates next to each other?

问题描述

我在接受采访时被问到这个问题：

如何随机关联一个没有两个副本的字符数组？ / p>

我想出的算法是：

1. 有一个 HashMap 的Character，字符对的出现次数。
   这样可以找到重复对唯一元素的数量。


2. 如果重复>唯一，则不能形成一个没有2
   重复元素的混洗数组？）


3. 如果unique> = duplicate，有2个堆栈 - 1个包含唯一的
   个字符，一个包含重复的字符。构造
   的结果数组，从而首先从唯一的栈
   中弹出一个元素，然后从重复堆栈中弹出一个元素。重复

例如：

  [a，b，b，c]具有上述算法的混洗数组 -  [a，b，c，b]; 
 
 [b，b，b，c] unique<重复返回错误
  

但我确信我的逻辑过于复杂。有没有一个更容易和笨蛋的方式来做到这一点？

解决方案

案例1：构建基本算法

1. 使用hashmap（键是字符，它的出现是值）来计算出现次数。这将给我们的桶，就像我们有cbaaba将给出3个桶与'c'值为1，'a'值为3，'b'值为2。




2. 根据最先发生的元素的出现排序水桶。
   所以现在我们有

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

3. 从最大出货桶中获取元素，将其数量减少1，并将其放在在结果数组中。根据排序的发生数据桶，跟随此后续的存储桶。

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

abc，现在我们将这些桶作为'a' - > 2，'b' - > 1和'c' - > 0

接下来，我们再次尝试从排序的桶中获取元数据（忽略含有0个元素的桶）

abcab现在我们桶状态变为：'a' - > 1，'b'-> 0和'c' - > 0

如上所述，我们继续将我们的结果作为

=>abcaba。

情况2：如果字符串如aaaabbbcccdd / strong>

我们将具有

 '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

  '一个'  - > 2 
'bc' - > 1 
'd' - > 0 
  

=> result =abcdabcdabc

  '一个'  - > 1 
'bc' - > 0 
'd' - > 0 
  

=>最终结果=abcdabcdabca

I was asked this question in an interview:

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

The algorithm I came up with was :

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

For example:

[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?

解决方案

Case 1 : Build the basic algorithm

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.

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

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

3. Get the element from max occurance bucket, decrease its count by 1 in map and put it in result array. Follow this for subsequent occuance buckets based on the sorted occurance buckets.

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

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

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

"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".

Case 2 : if string is like "aaaabbbcccdd"

We will have buckets as

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

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.

Now our buckets will be

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

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

=>result = "abcd"

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

=>result = "abcdabcd"

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

=>result = "abcdabcdabc"

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

=>Final Result = "abcdabcdabca"

这篇关于如何随机播放一个没有两个副本的字符数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！