c - 通过一次删除一个字符来均衡字符串中的字符数

Question

我想通过执行最少的操作来均衡字符串中字符的频率。这里的一个操作是“一次删除一个字符”。字符串由小写英文字母组成。

例如给定字符串 "abcdab" ，在这里我可以删除一个 'a' 和一个 'b' 因此需要 2 个操作并且每个字符的频率将相等。

我也可以完全删除一个字符例如'aaaabbbc' 在此我可以删除一个 'c' 和一个 'a' 以使频率相等。

我找不到逻辑。任何人都可以建议算法吗？

Answer 1

让我先描述一个二次解，然后我们将它变成 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) 完成传递。