從字符串刪除重複，不使用HashMap和O（n）的時間複雜度

-4

微軟面試問題從字符串刪除重複，不使用HashMap和O（n）的時間複雜度

取下串重複，不使用HashMap和O（n）的時間複雜度

有一個解決方案在O（n ）時間複雜性，但面試問題具體提到沒有HASHMAP和O（n）時間。

任何指針的讚賞，因爲我不能認爲任何低於O（n日誌n）時間，它採用排序和使用O（n）空間。

來源

2013-06-18 Spandan

你的意思是「刪除重複的字符」？ –

是的，我的意思是一樣的。 – Spandan

SO較少涉及「是否可能」，更多涉及尋找實際解決方案。 –

你做了一種桶排序。

使包含每一個字符
數組make的相應字符包含它的計數的數組

我們使用2個數組這樣的唯一原因是因爲你明確禁止的哈希映射。不過，您可以代表這種結構。如果您允許將字符轉換爲int s，則只需使用1個數組。

由於我們假定的可能的字符數量有限，每個陣列將是恆定的大小，或O（1）

遍歷您的字符串，並增加count爲您找到每個char 。如果計數已經大於0，則發現有重複。

搜索的字符數組的特定字符需要O（1）時間，因爲有字符的數量有限。

你會做這個搜索N次的淨運行時間爲O（n）

如果數組是沒有好，比你可以做一個鏈表來保存值只有你找到了。它仍然是不變的，因爲鏈表的大小仍然受到可能字符數的限制。

如果你這樣做，你或多或少會做同樣的事情，除非它在美觀上看起來不像桶式分類策略。

來源

2013-06-18 19:14:59

哦，我說沒有額外的空間..這是問題actualy，否則hashmap解決方案是微不足道的n衆所周知。 – Spandan

預定義的固定大小（英文大小爲26）hashmap沒有額外的空間 –

@Spandan O（1）空間並不意味着沒有額外的空間。 – greatwolf

我可能有另一種解決方案，我認爲它更糟糕，但它適用於小字符數組。該算法如下：

我們指定每個字母從2開始一個素數 - 這將是我們的查找表。

我們找到所有數字的乘積。 - > O（n）

在一個循環中 - > O（n）我們檢查產品％k * k == 0如果是，我們找到了一個重複的k。

該溶液僅存儲1號，而將容易溢出。首要表格將佔用很多空間。

編輯：如果我們添加一個限制，即只有40個可用的唯一字符，我們可以使用歐拉二次多項式來查找素數。

P（N）= N * N - N + 41

這並不需要任何額外的空間，除了產品。

來源

2013-06-18 20:00:15

如果您只存儲1號碼，那麼您如何爲每個角色分配不同的素數？ –

@SamIam因爲我們有一組有限的字符，所以我們可以在 –

之前創建一個查找表。但是接下來我們又回到了OP與bucket-sort方法完全相同的抱怨。我們有'O（C）'存儲空間，'C'是合法字符的數量。 –

traverse the list for i= 0 to n-1 elements 
{ 
    check for sign of A[abs(A[i])] ; 
    if positive then 
    make it negative by A[abs(A[i])]=-A[abs(A[i])]; 
    else // i.e., A[abs(A[i])] is negative 
    this element (ith element of list) is a repetition 
}

您可以在數組中輕鬆修改0。在字符的情況下，您可以使用其整數代碼。

來源

2013-06-19 05:01:01

從字符串刪除重複，不使用HashMap和O（n）的時間複雜度

回答

相關問題