查找未排序的字符串數組中的重複項 - O（nlogn）

我得到了String散列值的數組，例如：「123-51s-12as-dasd1-das-41c-sadasdgt-31」。我需要找出是否有重複。問題是，我需要在O（nlogn）中找到它們。查找未排序的字符串數組中的重複項 - O（nlogn）

1）我的想法：

要做到這一點，我可以使用二進制搜索算法。但二進制搜索僅適用於排序的數組數組。所以我問：有沒有什麼辦法來排序字符串數組？

2）我打開任何其他答案。我的問題是： 如何查找未知字符串數組中的所有重複項 - nlogn。

來源

2013-05-19 Ariel Grabijas

如果使用哈希表，你可以找到重複的O（n）的時間。 – Gabe

我使用字符串表。這些字符串是散列值。 –

由於時間限制爲nlog(n)，您可以先安全地排序數組，然後從左向右掃描以檢查重複的字符串。

來源

2013-05-19 18:24:11

好的，所以：1.如何排序字符串數組，不能簡單地轉換爲int.2。如果我從左到右掃描'n'個元素。這意味着我會做n×n比較。它是O（n^2） –

1. Java可以對String進行排序; 2.你只需要比較當前和下一個，因爲它是排序的，如果兩個元素相同，它們將被排序爲彼此相鄰。 –

好的，謝謝。這解決了我的問題。 –

你可以使用Set<String>並通過循環數組來插入你的字符串：行數是O（n），插入是O（log（n））。如果.add()返回false，這是一個重複：

public Set<String> getDups(String[] hashes) 
{ 
    Set<String> all = new HashSet<String>(); 
    Set<String> ret = new HashSet<String>(); 
    for (final String hash: hashes) 
     if (!all.add(hash)) // already seen 
      ret.add(hash); 
    return ret; 
}

來源

2013-05-19 18:30:55 fge

'Set'本身沒有性能保證。 'HashSet'具有分期固定時間插入，而不是O（log（n））。 –

查找未排序的字符串數組中的重複項 - O（nlogn）

回答

相關問題