删除字符串中出现次数最少的字符
当我们处理字符串时，有时候需要找出出现次数最少的字符并将其从字符串中删除。这个问题在实际开发中经常会遇到，因此本篇文章将从多个角度分析如何解决这个问题。
方法一：哈希表
我们可以使用哈希表来记录每个字符出现的次数，然后再遍历一遍字符串，找出出现次数最少的字符并将其删除。
具体实现步骤如下：
1. 遍历字符串，将每个字符出现的次数记录在哈希表中。
2. 遍历哈希表，找出出现次数最少的字符。
3. 遍历字符串，删除出现次数最少的字符。
代码示例：
```
void deleteLeastAppearingChar(string &str) {
unordered_map
int least = INT_MAX;
for (char c : str) {
m[c]++;
}
for (auto p : m) {
least = min(least, p.second);
}
for (int i = 0; i < str.size(); i++) {
if (m[str[i]] == least) {
str.erase(i, 1);
i--;
}
}
}
```
时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 为字符串的长度。
方法二：桶排序
由于哈希表的空间复杂度比较高，我们可以使用桶排序来优化空间复杂度。
具体实现步骤如下：
1. 遍历字符串，将每个字符出现的次数记录在桶中。
2. 遍历桶，找出出现次数最少的字符。
3. 遍历字符串，删除出现次数最少的字符。
代码示例：
```
void deleteLeastAppearingChar(string &str) {
vector
int least = INT_MAX;
for (char c : str) {
bucket[c]++;
}
for (int num : bucket) {
if (num > 0 && num < least) {
least = num;
}
}
for (int i = 0; i < str.size(); i++) {
if (bucket[str[i]] == least) {
str.erase(i, 1);
i--;
}
}
}
```
时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 为字符串的长度。
方法三：双指针
我们也可以使用双指针来解决这个问题。具体实现步骤如下：
1. 遍历字符串，将每个字符出现的次数记录在数组中。
2. 使用双指针 i 和 j 遍历字符串，当 s[j] 出现次数等于最小值时，j 向右移动。
3. 当 s[j] 出现次数大于最小值时，将 s[i] 替换为 s[j]，同时将数组中 s[i] 和 s[j] 出现次数交换，并将 i 向右移动。
4. 当 j 遍历完整个字符串后，将字符串截取为前 i 个字符。
代码示例：
```
void deleteLeastAppearingChar(string &str) {
int counts[256] = {0};
for (char c : str) {
counts[c]++;
}
int i = 0, j = 0, least = INT_MAX;
while (j < str.size()) {
if (counts[str[j]] == least) {
j++;
} else if (counts[str[j]] > least) {
str[i++] = str[j];
swap(counts[str[i - 1]], counts[str[j]]);
} else {
least = counts[str[j]];
j++;
}
}
str = str.substr(0, i);
}
```
时间复杂度为 O(n)，空间复杂度为 O(1)，其中 n 为字符串的长度。
方法四：STL
最简单的方法是使用STL中的 sort、lambda 和 erase_if 函数。
代码示例：
```
void deleteLeastAppearingChar(string &str) {
unordered_map
for (char c : str) {
m[c]++;
}
auto it = min_element(m.begin(), m.end(),
[](const pair
return a.second < b.second;
});
str.erase(remove_if(str.begin(), str.end(),
[&](const char& c) {
return m[c] == it->second;
}),
str.end());
}
```
时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为字符串的长度。
