資料結構
網路
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 次瀏覽
