通過一次刪除一個字符來均衡字符串中的字符數

我想通過執行最小操作數來均衡字符串中字符的頻率。這裏有一個操作是「一次刪除一個字符」。字符串由小寫英文字母組成。通過一次刪除一個字符來均衡字符串中的字符數

E.g.給定字符串「abcdab」，在這裏我可以刪除一個「a」和一個「b」，因此需要2次操作並且每個字符的頻率將相等。

此外，我可以完全刪除一個字符例如， 'aaaabbbc'在這個我可以刪除一個'c'和一個'a'來使頻率相等。

我無法找到邏輯。可以有人提出這個算法嗎？

來源

2017-01-09 Gaurav

我無法知道如何以最少的步驟完成此操作。 – Gaurav

我找到了頻率，並試圖平衡最常見的頻率，但這種方法不起作用 – Gaurav

計算多少單個「一次移除一個字符」並將其用作搜索的上限。 – MrSmith42

讓我先介紹一個二次的解決方案，然後我們將使它爲O（n log n）的

將您的字符串的頻率列表：

4, 3, 1

然後，觀察到最後所有角色將共享的頻率將等於現有頻率中的一個。換句話說，最後的頻率將是4,3或1.在一個循環中嘗試每個頻率。一旦你確定了頻率，就很容易計算出使所有字符具有該頻率或零值所需的步數。這將是沿線的：

res = BIG; 
for (int idxOfFreqIWant = 0; idxOfFreqIWant < n; ++ idxOfFreqIWant) { 
    int cur = 0; 
    for (int i = 0; i < n; ++ i) { 
     // if element occurs >= the freq, we remove characters to make it equal to freq 
     if (a[i] >= a[idxOfFreqIWant]) cur += a[i] - a[idxOfFreqIWant]; 
     // otherwise we have to remove all occurences 
     else cur += a[i]; 
    } 
    if (cur < res) res = cur; 
}

現在，這是明顯的二次方。你可以使它成爲O（n log n），我只會描述高層次的想法：按降序對所有頻率進行排序，從左到右迭代，並保持到目前爲止所看到的頻率的總數和計數。現在當你修正一個頻率時，你知道所有具有較高頻率的字符的總數和數量，以及具有較低頻率的所有字符的總數和計數，從而可以計算cur而不迭代所有元素，因此在一段時間內進行一次更新。總的複雜性將是O(n log n)排序+ O(n)做通過。

來源

2017-01-09 17:59:41 Ishamael

通過一次刪除一個字符來均衡字符串中的字符數

回答

相關問題