给一根绳子 str 对于小写字符，任务是删除重复项并返回结果字符串，而不修改原始字符串中字符的顺序。
null
例如：
Input: str = "geeksforgeeks"Output: geksforInput: str = "characters"Output: chartes
方法： 我们的想法是使用一些 柜台 变量来标记字符串中是否存在字符。要标记“a”的存在，请将第0位设置为1，对于“b”，请将第1位设置为1，依此类推。如果原始字符串中存在的字符的对应位设置为0，则表示该字符是该字符的第一个匹配项，因此将其对应位设置为1，并继续将当前字符包含在结果字符串中。
考虑字符串STR =“GeksFrEGEKEX”
- 角色：“g” x=6（g-97的ascii码） 计数器中的第6位未设置，导致字符“g”首次出现。 str[0]=“g” 计数器=000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 长度=1
- 角色：“e” x=4（e-97的ascii码） 计数器中的第四位未设置，导致字符“e”首次出现。 str[1]=“e” 计数器=0000000000000000000 1010000//将第四位标记为已访问 长度=2
- 角色：“e” x=4（e-97的ascii码） 计数器中的第4位被设置，导致重复字符。 忽略这个角色。移动到下一个角色。 计数器=0000000000000000000 1010000// 长度=2
- 角色：“k” x=10（ascii为k-97） 计数器中的第10位未设置，导致字符“k”首次出现。 str[2]=“k” 计数器=000000000000000 100001010000//标记第10位为已访问 长度=3
同样地，对所有角色都执行相同的操作。 结果字符串： geksfor（从索引0开始的长度为7的字符串）
算法：
- 初始化一个计数器变量（跟踪字符串中访问的字符），它最初是一个32位整数，表示为（00000000000000000000000000）。
- 把“A”当作零位计数器，“B”作为第一位计数器，“C”作为第二位计数器等等。
- 遍历输入字符串的每个字符。
- 获取字符的值，其中字符的值（x）=字符-97的Ascii。这将确保“a”的值为0，“b”的值为1，依此类推。
- 检查计数器的第X位。
- 如果计数器的第X位为0，这意味着当前字符第一次出现，请将当前字符保持在字符串的索引“长度”处。
- 通过设置计数器的第X位来标记当前访问的字符。
- 增量长度。
- 从索引0返回大小为“length”的子字符串。
以下是上述方法的实施情况：
C++
// C++ implementation of above approach #include <bits/stdc++.h> #include <string> using namespace std; // Function to remove duplicates string removeDuplicatesFromString(string str) { // keeps track of visited characters int counter = 0; int i = 0; int size = str.size(); // gets character value int x; // keeps track of length of resultant string int length = 0; while (i < size) { x = str[i] - 97; // check if Xth bit of counter is unset if ((counter & (1 << x)) == 0) { str[length] = 'a' + x; // mark current character as visited counter = counter | (1 << x); length++; } i++; } return str.substr(0, length); } // Driver code int main() { string str = "geeksforgeeks" ; cout << removeDuplicatesFromString(str); return 0; } |
JAVA
// Java implementation of above approach import java.util.Arrays; class GFG { // Function to remove duplicates static char [] removeDuplicatesFromString(String string) { // keeps track of visited characters int counter = 0 ; char [] str = string.toCharArray(); int i = 0 ; int size = str.length; // gets character value int x; // keeps track of length of resultant String int length = 0 ; while (i < size) { x = str[i] - 97 ; // check if Xth bit of counter is unset if ((counter & ( 1 << x)) == 0 ) { str[length] = ( char )( 'a' + x); // mark current character as visited counter = counter | ( 1 << x); length++; } i++; } return Arrays.copyOfRange(str, 0 , length); } // Driver code public static void main(String[] args) { String str = "geeksforgeeks" ; System.out.println(removeDuplicatesFromString(str)); } } // This code is contributed by Mithun Kumar |
Python3
# Python3 implementation of above approach # Function to remove duplicates def removeDuplicatesFromString(str2): # keeps track of visited characters counter = 0 ; i = 0 ; size = len (str2); str1 = list (str2); # gets character value x = 0 ; # keeps track of length of resultant string length = 0 ; while (i < size): x = ord (str1[i]) - 97 ; # check if Xth bit of counter is unset if ((counter & ( 1 << x)) = = 0 ): str1[length] = chr ( 97 + x); # mark current character as visited counter = counter | ( 1 << x); length + = 1 ; i + = 1 ; str2 = ''.join(str1); return str2[ 0 :length]; # Driver code str1 = "geeksforgeeks" ; print (removeDuplicatesFromString(str1)); # This code is contributed by mits |
C#
// C# implementation of above approach using System; class GFG { // Function to remove duplicates static string removeDuplicatesFromString( string string1) { // keeps track of visited characters int counter = 0; char [] str = string1.ToCharArray(); int i = 0; int size = str.Length; // gets character value int x; // keeps track of length of resultant String int length = 0; while (i < size) { x = str[i] - 97; // check if Xth bit of counter is unset if ((counter & (1 << x)) == 0) { str[length] = ( char )( 'a' + x); // mark current character as visited counter = counter | (1 << x); length++; } i++; } return ( new string (str)).Substring(0, length); } // Driver code static void Main() { string str = "geeksforgeeks" ; Console.WriteLine(removeDuplicatesFromString(str)); } } // This code is contributed by mits |
PHP
<?php // PHP implementation of above approach // Function to remove duplicates function removeDuplicatesFromString( $str ) { // keeps track of visited characters $counter = 0; $i = 0; $size = strlen ( $str ); // gets character value $x = 0; // keeps track of length of resultant string $length = 0; while ( $i < $size ) { $x = ord( $str [ $i ]) - 97; // check if Xth bit of counter is unset if (( $counter & (1 << $x )) == 0) { $str [ $length ] = chr (97 + $x ); // mark current character as visited $counter = $counter | (1 << $x ); $length ++; } $i ++; } return substr ( $str , 0, $length ); } // Driver code $str = "geeksforgeeks" ; echo removeDuplicatesFromString( $str ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript implementation of above approach // Function to remove duplicates function removeDuplicatesFromString(string) { // keeps track of visited characters let counter = 0; let str = string.split( "" ); let i = 0; let size = str.length; // gets character value let x; // keeps track of length of resultant String let length = 0; while (i < size) { x = str[i].charCodeAt(0) - 97; // check if Xth bit of counter is unset if ((counter & (1 << x)) == 0) { str[length] = String.fromCharCode( 'a' .charCodeAt(0) + x); // mark current character as visited counter = counter | (1 << x); length++; } i++; } return str.join( "" ).slice(0,length); } // Driver code let str = "geeksforgeeks" ; document.write(removeDuplicatesFromString(str)); // This code is contributed by patel2127 </script> |
输出：
geksfor
时间复杂性： O（n） 空间复杂性： O（n）->因为它使用字符串的char[]数组来存储字符串的字符（即，取决于输入字符串的长度）
另一种方法： 这种方法通过 大小为256的整数数组 （所有可能的字符）。 想法如下：
- 创建一个大小为256的整数数组，以便跟踪所有可能的字符。
- 迭代输入字符串，对于每个字符：
- 使用 ASCII码 作为索引的字符值：
- 如果索引处的值为0，则将字符复制到原始输入数组中，并增加endIndex，同时将索引处的值更新为-1。
- 否则跳过角色。
以下是上述方法的实施情况：
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Method to remove duplicates string removeDuplicatesFromString(string str) { // Table to keep track of visited characters vector< int > table(256, 0); vector< char > chars; for ( auto i : str) chars.push_back(i); // To keep track of end index of // resultant string int endIndex = 0; for ( int i = 0; i < chars.size(); i++) { if (table[chars[i]] == 0) { table[chars[i]] = -1; chars[endIndex++] = chars[i]; } } string ans = "" ; for ( int i = 0; i < endIndex; i++) ans += chars[i]; return ans; } // Driver code int main() { string str = "geeksforgeeks" ; cout << (removeDuplicatesFromString(str)) << endl; } // This code is contributed by Mohit kumar 29 |
JAVA
//Java implementation of above approach import java.util.Arrays; class GFG { // Method to remove duplicates static char [] removeDuplicatesFromString(String string) { //table to keep track of visited characters int [] table = new int [ 256 ]; char [] chars = string.toCharArray(); //to keep track of end index of resultant string int endIndex = 0 ; for ( int i = 0 ; i < chars.length; i++) { if (table[chars[i]] == 0 ) { table[chars[i]] = - 1 ; chars[endIndex++] = chars[i]; } } return Arrays.copyOfRange(chars, 0 , endIndex); } // Driver code public static void main(String[] args) { String str = "geeksforgeeks" ; System.out.println(removeDuplicatesFromString(str)); } } // This code is contributed by Sonu Singh |
Python3
# Python3 implementation of above approach # Method to remove duplicates def removeDuplicatesFromString(string): # Table to keep track of visited # characters table = [ 0 for i in range ( 256 )] # To keep track of end index # of resultant string endIndex = 0 string = list (string) for i in range ( len (string)): if (table[ ord (string[i])] = = 0 ): table[ ord (string[i])] = - 1 string[endIndex] = string[i] endIndex + = 1 ans = "" for i in range (endIndex): ans + = string[i] return ans # Driver code if __name__ = = '__main__' : temp = "geeksforgeeks" print (removeDuplicatesFromString(temp)) # This code is contributed by Kuldeep Singh |
C#
// C# implementation of above approach using System; class GFG { // Method to remove duplicates static char [] removeDuplicatesFromString(String str) { // table to keep track of visited characters int [] table = new int [256]; char [] chars = str.ToCharArray(); // to keep track of end index // of resultant string int endIndex = 0; for ( int i = 0; i < chars.Length; i++) { if (table[chars[i]] == 0) { table[chars[i]] = -1; chars[endIndex++] = chars[i]; } } char []newStr = new char [endIndex]; Array.Copy(chars, newStr, endIndex); return newStr; } // Driver code public static void Main(String[] args) { String str = "geeksforgeeks" ; Console.WriteLine(removeDuplicatesFromString(str)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of above approach // Method to remove duplicates function removeDuplicatesFromString(string) { // table to keep track of visited characters let table = new Array(256); for (let i=0;i<table.length;i++) table[i]=0; let chars = string.split( "" ); // to keep track of end index of resultant string let endIndex = 0; for (let i = 0; i < chars.length; i++) { if (table[chars[i].charCodeAt(0)] == 0) { table[chars[i].charCodeAt(0)] = -1; chars[endIndex++] = chars[i]; } } let ans= "" ; for (let i=0;i<endIndex;i++) ans += chars[i] return ans; } // Driver code let str = "geeksforgeeks" ; document.write(removeDuplicatesFromString(str)); // This code is contributed by unknown2108 </script> |
输出：
geksfor
时间复杂性： O（n） 空间复杂性： O（n）->因为它使用字符串的char[]数组来存储字符串的字符（即，取决于输入字符串的长度） 这种方法是由 索努辛格 .
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
