Algorithm to find the duplicate numbers in an array ---Fastest Way

algorithm, c

Solution

This can be solved elegantly using Linq:

public static void Main(string[] args)
{
    List<int> list = new List<int> { 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);
}

Internally it probably uses hashing to partition the list, but the code hides the internal details - here we are only telling it what to calculate. The compiler / runtime is free to choose how to calculate it, and optimize as it sees fit. Thanks to Linq this same code will run efficiently whether run an a list in memory, or if the list is in a database. In real code you should use this, but I guess you want to know how internally it works.

A more imperative approach that demonstrates the actual algorithm is as follows:

    List<int> list = new List<int> { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (int item in list)
    {
        if (!counts.ContainsKey(item))
        {
            counts[item] = 1;
        }
        else
        {
            counts[item]++;
        }
    }

    foreach (KeyValuePair<int, int> item in counts)
        Console.WriteLine("Item {0} has count {1}", item.Key, item.Value);

Here you can see that we iterate over the list only once, keeping a count for each item we see on the way. This would be a bad idea if the items were in a database though, so for real code, prefer to use the Linq method.

Problem

Original source