以下用於查找不同字符串的算法是否有效？

我最近發現了一句這樣的問題：以下用於查找不同字符串的算法是否有效？

"Given an array of strings, return the number of distinct strings in that array."

我想出了這個解決方案：

1. Get number_of_strings, which equals the number of strings in the input array 
2. Get number_of_non_redundant, which equals the length of the input array cast as a set 
3. Return 2 times number_of_non_redundant - number_of_strings

所以，我的問題是，確實爲所有數據集，該算法的工作？

來源

2012-08-15 mjgpy3

2次non_redundant - num_strings來自哪裏？不僅僅是這套作品的長度？ – 2012-08-15 17:40:52

是不是'number_of_non_redundant'已經是答案？ – Chris 2012-08-15 17:41:12

正如其他人指出，將需要更長的時間來解決這個問題的理想方式是散列法，簡單地返回number_of_non_redundant似乎是解決此問題的答案。

這裏是用於確定number_of_non_redundant一個可能的解決方案：

1）創建哈希集合（語言特定的）

2）通過整個陣列迭代，到陣列檢查中的每個元素看看哈希集中的元素是否存在，如果不存在，則添加它。

3）返回哈希集的大小。

使用哈希集在這裏提供恆定時間操作（添加，包含）。

此外，我想指出，你不能（至少我不知道這是一種語言）只是鑄數組到一組。鑄造是一個恆定時間的操作。這些是兩種不同的數據結構，爲了從數組中獲取元素並將它們放置在一個集合中，它需要遍歷數組並將元素輸入到集合中。

來源

2012-08-15 18:07:29

考慮字符串數組["a", "a", "a", "d", "d", "d"]。

number_of_strings是6; number_of_non_redundant爲2.您建議返回2 * 2 - 6 = -2。所以...不，你的算法不適用於所有數據集。

除非我很大地誤解了這個問題，不過，只要返回number_of_non_redundant就會一直有效，因爲它是你想返回的定義。 :)

來源

2012-08-15 17:40:35 Dougal

謝謝，這是一個非常可靠的答案。 – mjgpy3 2012-08-15 18:06:13

如何首先按照字典順序對數組進行排序，然後用一個標誌變量遍歷它，以跟蹤元素i-th和（i-1）-th之間的變化。

來源

2012-08-15 17:57:24 linello

該算法不是適用於所有數據集。它可能適用於特定的例子。

say n = number of non redundant strings 
p = number of strings in original array

根據您2n-p = n => n= p

你的算法工作，只有當(number of non redundant strings = length of original array)，這意味着只有當原數組是一組。

只給一個提示，如果你有足夠的可用內存，或者您可以使用排序的地方做，但比起散列

來源

2012-08-15 18:00:33 Jeff

以下用於查找不同字符串的算法是否有效？

回答

相關問題