本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
- Java
- Python3
- C#
例子：
Input: str = "lsbinforlsbin"
Output: lsbinforInput: str = "characters"
Output: chartes方法：这个想法是使用计数器变量以标记字符串中是否存在字符。要标记" a"的存在, 请将第0位设置为1, 为" b"将第1位设置为1, 依此类推。如果原始字符串中存在的字符的相应位设置为0, 则表示它是该字符的首次出现, 因此将其相应位设置为1, 并继续在结果字符串中包括当前字符。
【如何使用O(1)额外空间从字符串中删除重复项（）】考虑字符串str =" lsbinforlsbin"算法：
字符：'g'
x = 6(g – 97的ascii)计数器中的第6位未设置, 导致首次出现字符'g'。
str [0] ='g'
计数器= 00000000000000000000000001000000 //将第6位标记为已访问
长度= 1
字符：'e'
x = 4(e – 97的ascii)
计数器中的第4位未设置, 导致首次出现字符'e '。
str [1] =‘e’
计数器= 00000000000000000000000001010000 //将第4位标记为已访问
长度= 2
字符：‘e’
x = 4(e – 97的ascii)
设置计数器的第4位将导致重复字符。
忽略此字符。移动到下一个字符。
计数器= 00000000000000000000000001010000 //与先前的
长度= 2
字符相同：'k'
x = 10(k的ascii – 97)计数器中的第10位未设置, 导致首次出现字符'k'。
str [2] ='k'
计数器= 00000000000000000000010001010000 //将第10位标记为已访问
长度= 3
类似地, 对所有字符都执行相同的操作。
结果字符串：lsbinfor(从索引0开始的长度为7的字符串)
- 初始化一个计数器变量(保持跟踪字符串中访问的字符), 它是一个32位整数, 最初表示为(00000000000000000000000000000000)。
- 假设" a"为计数器的第0位, " b"为计数器的第1位, " c"为计数器的第2位, 依此类推。
- 遍历输入字符串的每个字符。
- 获取角色的值, 其中角色的值(x)=角色的Ascii –97。这将确保将'a'的值设置为0, 将'b'的值设置为1, 依此类推。
- 检查计数器的第x位。
- 如果计数器的第X位为0, 则表示当前字符是第一次出现, 请将当前字符保留在string的"长度"索引处。
- 通过设置计数器的第x位来标记当前访问的字符。
- 增量长度。
- 从索引0返回大小为"长度"的子字符串。
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 = "lsbinforlsbin" ;
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 = "lsbinforlsbin" ;
System.out.println(removeDuplicatesFromString(str));
}
}
// This code is contributed by Mithun KumarPython3
# 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 = "lsbinforlsbin" ;
print (removeDuplicatesFromString(str1));
# This code is contributed by mitsC#
// 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 = "lsbinforlsbin" ;
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 = "lsbinforlsbin" ;
echo removeDuplicatesFromString( $str );
// This code is contributed by mits
?>
输出如下：
lsbinfor时间复杂度：O(n)
空间复杂度：O(n)->由于它使用char []字符串数组来存储字符串字符(即取决于输入字符串的长度)
另一种方法：这种方法通过一个大小为256的整数数组(所有可能的字符)跟踪给定输入字符串中已访问的字符。
这个想法如下：
- 创建一个大小为256的整数数组, 以便跟踪所有可能的字符。
- 遍历输入字符串和每个字符：
- 使用ASCII码字符值作为索引：
- 如果index处的值为0, 则将字符复制到原始输入数组中并增加endIndex, 同时将index处的值更新为-1。
- 否则跳过角色。
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 = "lsbinforlsbin" ;
System.out.println(removeDuplicatesFromString(str));
}
}
// This code is contributed by Sonu SinghPython3
# 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 + = 1ans = ""
for i in range (endIndex):
ans + = string[i]return ans
# Driver code
if __name__ = = '__main__' :temp = "lsbinforlsbin"print (removeDuplicatesFromString(temp))# This code is contributed by Kuldeep SinghC#
// 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 = "lsbinforlsbin" ;
Console.WriteLine(removeDuplicatesFromString(str));
}
}
// This code is contributed by 29AjayKumar输出如下：
lsbinfor时间复杂度：O(n)
空间复杂度：O(n)-> 由于它使用char []字符串数组来存储字符串字符(即取决于输入字符串的长度)
推荐阅读
- Linux如何使用kill命令（用法示例）
- JavaScript如何使用DataView.getFloat32()方法（示例）
- 如何在Java中创建不可变类（代码示例）
- C#如何使用数组与数组列表（用法示例和区别）
- 操作系统中的页面替换算法详细指南
- 电脑无法识别U盘?本文教您怎样处理这个问题
- u盘插电脑没反应,本文教您处理u盘插电脑没反应
- u盘里面的数据会不会消失,本文教您u盘里面的数据消失怎样办
- 怎样进入bios设置,本文教您戴尔笔记本怎样进入bios设置