從字符串中刪除重複字符的算法

讓我們有一個字符串「abbashbhqa」。我們必須以輸出應該是「abshq」的方式刪除重複的字符。一種可能的解決方案是檢查字符串中存在的其他字符，然後進行操作。但是這需要O（n^2）時間複雜度。有沒有優化的方法來做到這一點？從字符串中刪除重複字符的算法

來源

2016-08-14 Soumya Kanti Naskar

添加到查找表（這將放棄重複），保持th e訂單。按照第一次出現的順序輸出。 – 2016-08-14 10:01:48

嘗試評論之前downvoting。 –

@Boris你能解釋什麼是查找表？ –

爲O（n）：

定義布爾的陣列L [26]。全部設置爲FALSE。構造一個新的空字符串

遍歷字符串併爲每個字母檢查L [x]是否爲FALSE。如果是，則將x附加到新字符串並將L [x]設置爲1.

將新字符串複製到舊字符串。

來源

2016-08-14 10:09:35

只要你迭代字符串，你創建一個集合（或哈希集合）。如果字母表是有限的（英文字母，如你的例子），你可以創建一個256布爾數組，並使用ASCII碼作爲它的關鍵。在開始時讓所有的布爾值都是錯誤的。每次迭代檢查array []是否爲false或true。如果它是假的，符號不是重複的，所以你把它標記爲array [] = true，不要從字符串中移除並繼續。在情況下，它是真的 - 符號是重複

來源

2016-08-14 10:06:58

也許這將是上述問題的實施

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)); 
    } 
}

來源

2016-08-15 18:52:58

我使用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)

來源

2016-08-15 19:04:10

從字符串中刪除重複字符的算法

回答

相關問題