問題描述
我在一次采訪中被問到這個問題:
I was asked this question in an interview:
如何洗牌沒有兩個相鄰的重復字符數(shù)組?
How to shuffle a character array with no two duplicates next to each other?
我想出的算法是:
- 有一個
HashMap的字符，字符對的出現(xiàn)次數(shù).以此計算重復元素和唯一元素的數(shù)量. - 如果重復 > 唯一，則不能形成沒有 2 的 shuffled 數(shù)組相鄰的重復元素 (?)
- 如果唯一 >= 重復，則有 2 個堆棧 - 1 個包含唯一字符和一個包含重復字符的字符.構建以這樣的方式生成數(shù)組，從唯一堆棧中彈出一個元素首先從重復堆棧中彈出一個元素.重復
- have a
HashMapof Character, count of occurrence of Character pairs. With this find the count of duplicate vs unique elements. - If duplicate > unique, cannot form a shuffled array with no 2 duplicate elements next to each other (?)
- 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
案例一:構建基本算法
使用哈希圖(鍵是字符，其出現(xiàn)次數(shù)是值)來計算出現(xiàn)次數(shù).這將為我們提供桶，就像如果我們有cbaaba"，將提供 3 個桶，其中 'c' 的值為 1，'a' 的值為 3，'b' 的值為 2.
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.
根據(jù)出現(xiàn)次數(shù)最多的元素對桶進行排序.所以現(xiàn)在我們有
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
- 從最大出現(xiàn)桶中獲取元素，將其在map中的計數(shù)減1并放入結果數(shù)組中.根據(jù)已排序的出現(xiàn)桶，請按照此操作獲取后續(xù)的占用桶.
結果數(shù)組將以排序方式從 3 個桶中各取一個開始.
result array will start with taking one each from 3 buckets in sorted fashion.
"abc" 現(xiàn)在我們的桶為 '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" 現(xiàn)在我們的桶狀態(tài)變?yōu)?'a'-> 1 ，'b'-> 0 和 'c'-> 0
"abcab" now our buckets state become as : 'a'-> 1 , 'b'- > 0 and 'c'-> 0
接下來我們繼續(xù)得到我們的結果
next as above we proceed to have our result as
=> "abcaba".
=> "abcaba".
案例 2:如果字符串類似于 "aaaabbbcccdd"
我們將有桶作為
'a'--> 4
'b'--> 3
'c'--> 3
'd'--> 2
這里我們有一桶 b 和 c 大小相同.當這種情況發(fā)生時，我們必須執(zhí)行 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.
現(xiàn)在我們的桶將是
'a'--> 4
'bc'--> 3
'd'--> 2
現(xiàn)在以與案例 1 相同的方式繼續(xù)進行，我們嘗試構建結果
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"
這篇關于如何洗牌一個沒有兩個重復的字符數(shù)組?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！