0

我最近发现了一个类似的问题:

"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

所以,我的问题是,这个算法是否适用于所有数据集?

4

4 回答 4

4

考虑字符串数组["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-15T17:40:35.130 回答
2

正如其他人所指出的,简单地返回number_of_non_redundant似乎是这个问题的答案。

这是确定的可能解决方案number_of_non_redundant

1)创建一个哈希集(特定于语言)

2)遍历整个数组,在数组的每个元素上检查该元素是否存在于哈希集中,如果不存在,则添加它。

3) 返回哈希集的大小。

在此处使用哈希集提供了恒定时间操作(添加、包含)。

此外,我想指出您不能(至少我在语言中不知道这一点)简单地数组转换为集合。铸造是一个恒定的时间操作。这是两种不同的数据结构,为了从数组中获取元素并将它们放入集合中,需要遍历数组并将元素输入到集合中。

于 2012-08-15T18:07:29.133 回答
0

首先按字典顺序对数组进行排序,然后使用标志变量循环遍历它,以跟踪元素 i-th 和 (i-1)-th 之间的变化?

于 2012-08-15T17:57:24.753 回答
0

此算法不适用于所有数据集。不过,它可能适用于特定示例。

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-15T18:00:33.460 回答