我最近发现了一个类似的问题：
"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
所以，我的问题是，这个算法是否适用于所有数据集？
考虑字符串数组["a", "a", "a", "d", "d", "d"]。
number_of_strings是 6；number_of_non_redundant是 2. 你提议退货2 * 2 - 6 = -2。所以...不，您的算法不适用于所有数据集。
除非我对这个问题有很大的误解，否则只是返回number_of_non_redundant总是有效的，因为它是你想要返回的定义。:)
正如其他人所指出的，简单地返回number_of_non_redundant似乎是这个问题的答案。
这是确定的可能解决方案number_of_non_redundant：
1）创建一个哈希集（特定于语言）
2）遍历整个数组，在数组的每个元素上检查该元素是否存在于哈希集中，如果不存在，则添加它。
3) 返回哈希集的大小。
在此处使用哈希集提供了恒定时间操作（添加、包含）。
此外，我想指出您不能（至少我在语言中不知道这一点）简单地将数组转换为集合。铸造是一个恒定的时间操作。这是两种不同的数据结构，为了从数组中获取元素并将它们放入集合中，需要遍历数组并将元素输入到集合中。
首先按字典顺序对数组进行排序，然后使用标志变量循环遍历它，以跟踪元素 i-th 和 (i-1)-th 之间的变化？
此算法不适用于所有数据集。不过，它可能适用于特定示例。
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)，这意味着仅当原始数组是一个集合时。
只是提示一下，如果您有足够的可用内存，则解决此问题的理想方法是散列，或者您可以使用排序就地进行，但与散列相比需要更长的时间