从字符串中删除重复字符的算法

问题描述：

让我们有一个字符串“abbashbhqa”。我们必须以输出应该是“abshq”的方式删除重复的字符。一种可能的解决方案是检查字符串中存在的其他字符，然后进行操作。但是这需要O（n^2）时间复杂度。有没有优化的方法来做到这一点？从字符串中删除重复字符的算法

添加到查找表（这将放弃重复），保持th e订单。按照第一次出现的顺序输出。 – 2016-08-14 10:01:48

尝试评论之前downvoting。 –

@Boris你能解释什么是查找表？ –

答

为O（n）：

定义布尔的阵列L [26]。全部设置为FALSE。构造一个新的空字符串

遍历字符串并为每个字母检查L [x]是否为FALSE。如果是，则将x附加到新字符串并将L [x]设置为1.

将新字符串复制到旧字符串。

答

只要你迭代字符串，你创建一个集合（或哈希集合）。如果字母表是有限的（英文字母，如你的例子），你可以创建一个256布尔数组，并使用ASCII码作为它的关键。在开始时让所有的布尔值都是错误的。每次迭代检查array []是否为false或true。如果它是假的，符号不是重复的，所以你把它标记为array [] = true，不要从字符串中移除并继续。在情况下，它是真的 - 符号是重复

答

也许这将是上述问题的实施

import java.util.*; 
import java.io.*; 

public class String_Duplicate_Removal 
{ 

    public static String duplicate_removal(String s) 
    { 
     if(s.length()<2) 
      return s; 

     else if(s.length()==2) 
     { 
      if(s.charAt(0)==s.charAt(1)) 
       s = Character.toString(s.charAt(0)); 
      return s; 
     } 

     boolean [] arr = new boolean[26]; 

     for(int i=0;i<s.length();i++) 
     { 

      if(arr[s.charAt(i)-'a']==false) 
       arr[s.charAt(i)-'a']=true; 

      else 
      { 
       s= ((new StringBuilder(s)).deleteCharAt(i)).toString(); 
       i--; 
      } 
     } 
     return s; 
    } 

    public static void main(String [] args) 
    { 
     String s = "abbashbhqa"; 
     System.out.println(duplicate_removal(s)); 
    } 
}

答

我使用Python的解决和工作在O（n）的时间和O（n）的空间 - 我使用集（）因为设置不允许重复--- 在这种情况下，元素的顺序发生变化 - 如果你想让订单保持不变，那么你可以使用OrderedDict（），它也适用于O（n）时间 -

def remove_duplicates(s , ans_set):  
    for i in s:     # O(n) 
     ans_set.add(i)   # O(1) 
    ans = '' 
    for char in ans_set: 
     ans += char 
    print ans 

s = raw_input() 
ans_set = set() 
remove_duplicates(s , ans_set) 

from collections import OrderedDict 
def remove_duplicates_maintain_order(a):     
    ans_dict = OrderedDict() 
    for i in a:           # O(n) 
     ans_dict[i] = ans_dict.get(i , 0) + 1   # O(1) 
    ans = '' 
    for char in ans_dict: 
      ans += char 
    print ans 

s = raw_input() 
remove_duplicates_maintain_order(s)

从字符串中删除重复字符的算法

相关推荐