Find duplicates in an array of integers: S = {0...n}. Complexity is equals to O(n)
public static int[] FindDuplicates(int[] array, int range)
{
if (range == 0)
{
throw new ArgumentOutOfRangeException("range", "Range must be more than 0.");
}
int[] dups = new int[range];
int[] digitflags = new int[range];
int dupsCount = 0;
foreach (var number in array)
{
if (digitflags[number] <= 1) { digitflags[number]++; }
if (digitflags[number] > 1)
{
dups[number]++;
dupsCount++;
}
}
return dupsCount == 0 ? null : dups;
}