查找数组中重复数字的算法—最快的方法
我需要最快速，最简单的算法，在数组中找到重复的数字，也应该能够知道重复的数量。
例如：如果数组是{2,3,4,5,2,4,6,2,4,7,3,8,2}
我应该知道有4个，2个3个，3个4个。
创建一个哈希表，其中键是数组项，值是计数器在数组中出现相应数组项的次数。 这是一种有效的方法，但可能不是最快的方法。
像这样的东西（伪代码）。 您将通过Google搜索找到大量用于C的哈希映射实现 。
hash_map = create_new_hash_map() for item in array { if hash_map.contains_key(item){ counter = hash_map.get(item) } else { counter = 0 } counter = counter + 1 hash_map.put(item, counter) }
这可以使用Linq优雅地解决：
public static void Main(string[] args) { List list = new List { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 }; var grouping = list .GroupBy(x => x) .Select(x => new { Item = x.Key, Count = x.Count()}); foreach (var item in grouping) Console.WriteLine("Item {0} has count {1}", item.Item, item.Count); }
在内部，它可能使用散列来对列表进行分区，但代码隐藏了内部细节 – 这里我们只告诉它要计算什么 。 编译器/运行时可以自由选择如何计算它，并根据需要进行优化。 感谢Linq，无论是在内存中运行列表，还是列表都在数据库中，相同的代码都能高效运行。 在实际代码中你应该使用它，但我想你想知道它的内部工作原理。
演示实际算法的更为迫切的方法如下：
List list = new List { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 }; Dictionary counts = new Dictionary(); foreach (int item in list) { if (!counts.ContainsKey(item)) { counts[item] = 1; } else { counts[item]++; } } foreach (KeyValuePair item in counts) Console.WriteLine("Item {0} has count {1}", item.Key, item.Value);
在这里，您可以看到我们只对列表进行一次迭代，并对我们在路上看到的每个项目进行计数。 如果项目在数据库中，这将是一个坏主意，因此对于实际代码，更喜欢使用Linq方法。
这是一个用标准输入做的C版本; 它与输入的长度一样快（注意，命令行上的参数数量是有限的……）但是应该让你知道如何继续：
#include int main ( int argc, char **argv ) { int dups[10] = { 0 }; int i; for ( i = 1 ; i < argc ; i++ ) dups[atoi(argv[i])]++; for ( i = 0 ; i < 10 ; i++ ) printf("%d: %d\n", i, dups[i]); return 0; }
示例用法：
$ gcc -o dups dups.c $ ./dups 0 0 3 4 5 0: 2 1: 0 2: 0 3: 1 4: 1 5: 1 6: 0 7: 0 8: 0 9: 0
注意事项：
-
如果你打算计算10s，11s等的数量 - > dups []数组必须更大
-
左边的练习是从一系列整数中实现读数并确定它们的位置
如果您知道下限和上限，并且它们距离不太远，那么这将是使用Radix Sort的好地方。 由于这是家庭作业的气味，我将其留给OP阅读文章并实施算法。
您告诉我们关于输入数组的次数越多，我们制作算法的速度就越快。 例如，对于您的单位数字的示例，然后创建一个包含10个元素的数组（索引为0：9）并在数组的右侧元素中累积数字的出现次数（措辞不当，但您可能会抓住我的漂移）是可能比哈希更快。 （我说可能会更快，因为我没有做任何测量而不会）。
我同意大多数受访者认为哈希可能是最常见案例的正确方法，但总是值得考虑你的是否是一个特例。
如果你不想像这样使用哈希表或smtg，只需对数组进行排序然后计算出现次数，如下所示应该工作
Arrays.sort(array); lastOne=array's first element; count=0, for(i=0; i
如果数字的范围是已知的并且很小，您可以使用数组来跟踪您每次看到的次数（这本质上是一个桶排序）。 如果它很大，你可以对它进行排序，然后计算重复数据，因为它们将相互跟随。
您可以使用哈希表将每个元素值存储为键。 然后每次密钥已存在时递增+1。
使用散列表/关联数组/字典（所有相同的东西，但编程环境之间的术语变化）是要走的路。
作为python中的一个例子：
numberList = [1, 2, 3, 2, 1, ...] countDict = {} for value in numberList: countDict[value] = countDict.get(value, 0) + 1 # Now countDict contains each value pointing to their count
大多数编程语言中都存在类似的结构。
> I need the fastest and simple algorithm which finds the duplicate numbers in an array, also should be able to know the number of duplicates.
我认为最快的算法是计算数组中的重复项：
#include #include #include #include typedef int arr_t; typedef unsigned char dup_t; const dup_t dup_t_max=UCHAR_MAX; dup_t *count_duplicates( arr_t *arr, arr_t min, arr_t max, size_t arr_len ){ assert( min <= max ); dup_t *dup = calloc( max-min+1, sizeof(dup[0]) ); for( size_t i=0; i
注意：您不能在每个arrays上使用最快的算法。
代码首先对数组进行排序，然后将唯一元素移动到前面，跟踪元素的数量。 它比使用桶排序慢，但更方便。
#include #include static int cmpi(const void *p1, const void *p2) { int i1 = *(const int *)p1; int i2 = *(const int *)p2; return (i1 > i2) - (i1 < i2); } size_t make_unique(int values[], size_t count, size_t *occ_nums) { if(!count) return 0; qsort(values, count, sizeof *values, cmpi); size_t top = 0; int prev_value = values[0]; if(occ_nums) occ_nums[0] = 1; size_t i = 1; for(; i < count; ++i) { if(values[i] != prev_value) { ++top; values[top] = prev_value = values[i]; if(occ_nums) occ_nums[top] = 1; } else ++occ_nums[top]; } return top + 1; } int main(void) { int values[] = { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 }; size_t occ_nums[sizeof values / sizeof *values]; size_t unique_count = make_unique( values, sizeof values / sizeof *values, occ_nums); size_t i = 0; for(; i < unique_count; ++i) { printf("number %i occurred %u time%s\n", values[i], (unsigned)occ_nums[i], occ_nums[i] > 1 ? "s": ""); } }
选项1：哈希它。 选项2：对其进行排序，然后计算连续运行次数。
有一个“算法”，我一直用它来在Unix中的文件中找到重复的行：
sort file | uniq -d
如果在C中实现相同的策略，那么使用哈希表等更高级的策略来击败它是非常困难的。 调用排序算法，然后调用您自己的函数来检测排序列表中的重复项。 排序算法需要O（n * log（n））时间，uniq函数需要线性时间。 （Southern Hospitality提出了类似的观点，但我想强调的是，他所谓的“选项2”似乎比更流行的哈希表建议更简单，更快。）
计数排序是上述问题的答案。如果您看到计数排序的算法，您会发现有一个数组被保留用于保持原始数组中存在的元素的计数。
这是另一种解决方案，但它需要O（nlogn）时间。 使用Divide and Conquer方法使用合并排序对给定数组进行排序。 在合并排序中的合并步骤期间，通过比较两个排序子arrays中的元素来查找重复项。