数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 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] = True。
步骤 6：将写指针的值增加 1。
步骤 7：更新输入字符串，然后将计算出的字符串的最后一个字符分配为 NULL。
步骤 8：最后，在消除冗余字符后打印结果。
示例
#include <iostream>
using namespace std;
void removeDuplicatesFromStr(char inputString[]) {
// found is a Boolean array whose index mapped to the alphabets
bool present[26] = {false};
// write pointer, tells the place of writing
int write = -1;
//use for loop
for (int read = 0; inputString[read] != '\0'; ++read) {
// search bit to check character's repetition
int d = (int)inputString[read] - 97;
// if the character did not come yet
if (present[d] == false) {
present[d] = true;
write += 1;
inputString[write] = inputString[read];
}
}
// set last character of resultant string to 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;
}
输出
Input String for removing duplicates: learningmaterial Output String after removing duplicates: 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 被设置为 1。
对每个字符执行类似的操作。
这里，如果整数的位 d = 1，则表示映射到位 d 的字符已存在于字符串当前字符的左侧。因此，我们不再需要使用该字符。
如果整数的位 d = 0，则表示映射到位 d 的字符尚未出现，因此需要考虑它并将其插入到结果字符串中。
算法：removeDuplicates(str)
步骤 1：创建一个名为 found 的整数变量。
步骤 2：声明一个等于 -1 的写指针。
步骤 3：初始化 for 循环以查找用于检查重复的位。
步骤 4：设置整数 d = ASCII(str[read]) – 97。
步骤 5：如果 'd' 不存在于 'found' 中，则将 'd' 插入到 found 中。
步骤 6：将写指针的值增加 1。
步骤 7：更新输入字符串，然后将计算出的字符串的最后一个字符分配为 NULL。
步骤 8：最后，在消除冗余字符后打印结果。
示例
#include <iostream>
using namespace std;
void removeDuplicates(char inputStr[]) {
// found is an integer whose bits mapped to the alphabets
int found = 0;
// write pointer, tells the place of writing
int write = -1;
for (int read = 0; inputStr[read] != '\0'; ++read) {
// find bit for checking repetition
int d = (int)inputStr[read] - 97;
// if character not came yet
if ((found & (1<<d)) == 0) {
found = found | (1<<d);
write += 1;
inputStr[write] = inputStr[read];
}
}
// set last character of resultant string to NULL
inputStr[write+1] = '\0';
}
int main() {
char inputStr[10000];
int n;
cout << "Input String for removing duplicates: ";
cin >> inputStr;
removeDuplicates(inputStr);
cout << "Output String after removing duplicates: " << inputStr << endl;
return 0;
}
输出
Input String for removing duplicates: tutorialspoint Output String after removing duplicates: tuorialspn
程序的时间复杂度 = O(N)
程序的空间复杂度 = O(1)
在本文中，我们提供了两种方法来解决问题，使用 O(N) 的时间复杂度和 O(1) 的空间复杂度。
268 次浏览
