如何使用O(1)额外空间从字符串中删除重复项？

2021年3月28日13:28:42 发表评论 872 次浏览

本文概述

给定一个字符串str对于小写字符, 任务是删除重复项并返回结果字符串, 而无需修改原始字符串中字符的顺序。

例子：

Input: str = "lsbinforlsbin"
Output: lsbinfor

Input: str = "characters"
Output: chartes

方法：这个想法是使用计数器变量以标记字符串中是否存在字符。要标记" a"的存在, 请将第0位设置为1, 为" b"将第1位设置为1, 依此类推。如果原始字符串中存在的字符的相应位设置为0, 则表示它是该字符的首次出现, 因此将其相应位设置为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的字符串)

算法： 

  1. 初始化一个计数器变量(保持跟踪字符串中访问的字符), 它是一个32位整数, 最初表示为(00000000000000000000000000000000)。
  2. 假设" a"为计数器的第0位, " b"为计数器的第1位, " c"为计数器的第2位, 依此类推。
  3. 遍历输入字符串的每个字符。
  4. 获取角色的值, 其中角色的值(x)=角色的Ascii –97。这将确保将'a'的值设置为0, 将'b'的值设置为1, 依此类推。
  5. 检查计数器的第x位。
  6. 如果计数器的第X位为0, 则表示当前字符是第一次出现, 请将当前字符保留在string的"长度"索引处。
  7. 通过设置计数器的第x位来标记当前访问的字符。
  8. 增量长度。
  9. 从索引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 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 = "lsbinforlsbin" ;
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 = "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的整数数组(所有可能的字符)跟踪给定输入字符串中已访问的字符。

这个想法如下：

  1. 创建一个大小为256的整数数组, 以便跟踪所有可能的字符。
  2. 遍历输入字符串和每个字符：
  3. 使用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 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 = "lsbinforlsbin"
     
     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 = "lsbinforlsbin" ;
         Console.WriteLine(removeDuplicatesFromString(str));
     }
}
 
// This code is contributed by 29AjayKumar

输出如下：

lsbinfor

时间复杂度：O(n)

空间复杂度：O(n)->由于它使用char []字符串数组来存储字符串字符(即取决于输入字符串的长度)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: