在 O(1) 额外空间中从字符串中删除重复项
在此问题中，我们的任务是删除字符串中除每个字符的第一次出现之外的所有重复字符。此外，需要在不使用任何额外空间的情况下解决问题，并且空间复杂度必须为 O(1)。本文使用了各种方法。布尔数组在一种方法中定义以确定字符的重复，其中布尔数组的索引映射到每个字母表。在第二种方法中，使用位操作的概念从结果字符串中删除重复的字符。
让我们探索这篇文章，了解如何使用 Java 编程语言解决它。
向您展示一些实例
实例 1
如果字符串 = "tutorialspoint"
应用算法后 -
结果字符串 = "tuorialspn"
实例 2
如果字符串 = "learningmaterial"
应用算法后 -
结果字符串 = "learnigmt"
多种方法
我们提供了不同方法的解决方案。
通过使用大小为26
通过使用单个整数位。
方法 1:通过使用大小为 26 的布尔数组
为了解决这个问题，我们将使用一个包含 26 个元素的布尔数组。每个字母表都与布尔数组的索引映射，以告知字符的重复。
将英文字母映射到布尔数组
'a' ⇒ found[0] 'b' ⇒ found[1] 'c' ⇒ found[2] 'd' ⇒ found[3] . . . 'z' ⇒ found[25
这里，如果 found[i] = True，则表示映射到索引 - i 的字符已经存在于字符串当前字符的左侧。所以，我们不再需要使用该字符。
如果 found[i] = False，则意味着映射到索引 i 的字符尚未出现，因此需要考虑它并将其插入到结果字符串中。
算法:removeDuplicatesFromStr(str)
步骤 1:创建一个名为 found 的数组。
步骤 2:声明一个等于 -1 的写入指针。
步骤 3:启动 for 循环以遍历字符串"str"。
步骤 4:设置整数 d = ASCII(str[read]) – 97。
步骤 5:如果 found[d] = False，则设置 found[d] =正确。
步骤 6:将写入指针的值增加 1。
步骤 7:更新输入字符串，然后将计算字符串的最后一个字符赋值为 NULL。
步骤 8:最后，消除冗余字符后打印结果。
示例
#include <iostream>
using namespace std;
void removeDuplicatesFromStr(char inputString[]) {
// found 是一个布尔数组，其索引映射到字母表
bool present[26] = {false};
// 写入指针，指示写入位置
int write = -1;
//使用 for 循环
for (int read = 0; inputString[read] != '\0'; ++read) {
// 搜索位以检查字符的重复
int d = (int)inputString[read] - 97;
// 如果字符尚未出现
if (present[d] == false) {
present[d] = true;
write += 1;
inputString[write] = inputString[read];
}
}
// 将结果字符串的最后一个字符设置为 NULL
inputString[write+1] = '\0';
}
int main() {
char inputString[10000];
int N;
cout << "Input String for removing duplicates: ";
cin >> inputString;
removeDuplicatesFromStr(inputString);
cout << "Output String after removing duplicates: " << inputString << endl;
return 0;
}
输出
用于删除重复项的输入字符串:learningmaterial 删除重复项后的输出字符串:learnigmt
程序的时间复杂度 = O(N)
程序的空间复杂度 = O(26) = O(1)
方法 2:使用单个整数位
为了解决这个问题，我们创建一个整数，它的位告诉我们字符是否重复。
C++ 中整数的大小 = 4 字节 = 4*8 位 = 32 位。
英文字母表中的字符数 = 26
英文字母表的数量 <整数的位数，
因此，我们可以使用整数的单独位来表示英文字母表的每个字符。
英文字母表到整数的映射
'a' ⇒ bit 0 ⇒ (int)'a' - 97 'b' ⇒ bit 1 ⇒ (int)'b' - 97 'c' ⇒ bit 2 ⇒ (int)'c' - 97 'd' ⇒ bit 3 ⇒ (int)'d' - 97 . . . 'z' ⇒ bit 25 ⇒ (int)'z' - 97
如果字符串中出现"a"，则位 0 变为 SET。
对每个字符执行类似的操作。
这里，如果 Integer 的位 d = 1，则表示映射到位 d 的字符已经存在于字符串当前字符的左侧。所以，我们不再需要使用该字符。
如果 Integer 的位 d = 0，则表示映射到位 d 的字符尚未出现，因此需要考虑它并将其插入到结果字符串中。
算法:removeDuplicates(str)
步骤 1:创建一个名为 found 的 Integer 变量。
步骤 2:声明一个等于 -1 的写入指针。
步骤 3:启动 for 循环以查找用于检查重复的位。
步骤 4:设置整数 d = ASCII(str[read]) – 97。
步骤 5:如果"found"中不存在"d"，则将"d"插入找到。
步骤 6:将写入指针的值增加 1。
步骤 7:更新输入字符串，然后将计算字符串的最后一个字符也赋值为 NULL。
步骤 8:最后，消除冗余字符后打印结果。
示例
#include <iostream>
using namespace std;
void removeDuplicates(char inputStr[]) {
// found 是一个整数，其位映射到字母表
int found = 0;
// 写入指针，指示写入位置
int write = -1;
for (int read = 0; inputStr[read] != '\0'; ++read) {
// 查找用于检查重复的位
int d = (int)inputStr[read] - 97;
// 如果字符尚未出现
if ((found & (1<<d)) == 0) {
found = found | (1<<d);
write += 1;
inputStr[write] = inputStr[read];
}
}
// 将结果字符串的最后一个字符设置为 NULL
inputStr[write+1] = '\0';
}
int main() {
char inputStr[10000];
int n;
cout << "删除重复项的输入字符串:";
cin >> inputStr;
removeDuplicates(inputStr);
cout << "删除重复项后的输出字符串:" << inputStr << endl;
return 0;
}
输出
删除重复项的输入字符串:tutorialspoint 删除重复项后的输出字符串:tuorialspn
程序的时间复杂度 = O(N)
程序的空间复杂度 = O(1)
在本文中，我们给出了两种使用时间复杂度 O(N) 和空间复杂度 O(1) 解决问题的方法。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/
