Duplicate values in an int array (best performance)

Question

I have an array of numbers that have some duplicate values. I want to find the first two duplicate numbers.

The real problem is it must be in best performance and I cant use LINQ it must be in classic codes.

The real question is about best performance so it means best answer is the fastest language and fastest algorithm.

I tried it in C#:

        int[] numbers = {5, 2, 10, 18, 55, 100, 10, 50, 23, 6, 14, 25, 12};
        int result1 = -1;
        int result2 = -1;
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = 0; j < numbers.Length; j++)
            {
                if (numbers[j] == numbers[i] & i != j)
                {
                    result2 = j;
                    result1 = i;
                    J = numbers.Length;  //this will cause loop exit.
                    i = numbers.Length;  //this will cause first loop to exit.
                }
            }
        }

        Console.Write("The result of search is {0} and {1}", result1, result2);
        Console.ReadLine();

I will appreciate any answers ;)

How large is the array in practice and how are duplicates typically distributed? — NeilMacMullen
– NeilMacMullen, Commented May 17, 2014 at 10:39
Use break to cause the loop to exit, it is much more readable. — Cody Gray
– Cody Gray ♦, Commented May 17, 2014 at 10:40
@NeilMacMullen array's length is about 500 and duplicates are about 5 numbers. — HaMeD
– HaMeD, Commented May 17, 2014 at 10:43
Rollback the edit. Code after the break is not executed, so it now looks for the last duplicate instead of the first. — Guffa
– Guffa, Commented May 17, 2014 at 10:50

Guffa · Accepted Answer · 2014-05-17 10:56:49Z

3

Use a dictionary to store the numbers and where you found them, and when you find one that exists in the dictionary, you have your duplicate and its position. Adding and locating items in a dictionary are O(1) operations, so the algorighm is an O(n) operation:

int[] numbers = { 5, 2, 10, 18, 55, 100, 10, 50, 23, 6, 14, 25, 12 };
Dictionary<int, int> found = new Dictionary<int,int>();
int result1 = -1, result2 = -1;
for (int i = 0; i < numbers.Length; i++) {
  int number = numbers[i];
  int pos;
  if (found.TryGetValue(number, out pos)) {
    result1 = pos;
    result2 = i;
    break;
  }
  found.Add(number, i);
}
Console.Write("The result of search is {0} and {1}", result1, result2);
Console.ReadLine();

For some additional performance you can preallocate space for all the items in the dictionary that it might need. This uses more memory in the average case, but keeps the dictionary from repeatedly allocating more space when it grows:

Dictionary<int, int> found = new Dictionary<int,int>(numbers.Length);

edited May 17, 2014 at 10:56

answered May 17, 2014 at 10:46

Guffa

703k111 gold badges760 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

HaMeD Over a year ago

It's perfect;). I test it with a stopwatch and the result was amazing. my code done in 0.4638 MS and your code done in 0.1001 MS

HaMeD Over a year ago

Is there any structure like Dictionary in c++? Is there any way to implement it in c++ like this ?

Guffa Over a year ago

@HaMeD: That would be an std::unordered_map, so it would be possible to implement the same thing in C++.

Collectives™ on Stack Overflow

Duplicate values in an int array (best performance)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related