12

I'm reading the contents of file into a 9 element array. I need to check if there are any duplicates in this array. I need to do this without reordering or changing the any of the contents of the array.

How would I go about doing this?

nbro
  • 15,395
  • 32
  • 113
  • 196
Petefic
  • 657
  • 6
  • 14
  • 31
  • 1
    possible duplicate of [finding duplicates from the array of pointers](http://stackoverflow.com/questions/6425747/finding-duplicates-from-the-array-of-pointers) – Pubby Nov 20 '11 at 04:18

3 Answers3

21

Use brute force.

You've only got 9 elements in the array, so it'll only take 36 comparisons to find any duplicates:

int count = sizeof(array) / sizeof(array[0]);

for (int i = 0; i < count - 1; i++) { // read comment by @nbro
    for (int j = i + 1; j < count; j++) {
        if (array[i] == array[j]) {
            // do whatever you do in case of a duplicate
        }
    }
}
nbro
  • 15,395
  • 32
  • 113
  • 196
Caleb
  • 124,013
  • 19
  • 183
  • 272
  • 1
    By `sizeof(array)` you of course mean `sizeof(array) / sizeof(array[0])`? – Alexey Frunze Nov 20 '11 at 04:23
  • 1
    The first and outer loop only needs to go up to `count - 1`, because otherwise the inner loop at the last iteration is completely useless. I will edit the answer to reflect this improvement. – nbro Jun 09 '16 at 21:55
  • So simple. You should look at the same question in Java and all the inefficient answers it got. – Thomas Dec 27 '16 at 15:17
  • 1
    I am wondering and almost unable to figure out how did you count the comparison numbers @Caleb. If you have time, could you please elaborate a little bit about it? I am interested to know and forgot the actual way to do so. Thanks. – AT-2017 Oct 06 '17 at 20:12
  • 3
    @AT-2017 Say you've got 9 items in an array and want to compare each pair of items: start with the first one, and compare it to each of the other 8 items in the array. That's 8 comparisons so far. Then move to the second one. No need to compare it to the first item, you already did that, so compare to each of the remaining 7 items. Repeat this process and you'll end up with 8+7+6+5+4+3+2+1=36 comparisons. And that's just what the code above does. – Caleb Oct 06 '17 at 20:31
  • maybe you could update your answer for non-brute force method that scales? none of the other answers address that. – jangorecki Feb 06 '19 at 13:25
  • 2
    @jangorecki I could, but then I'd be answering a different question than the one the OP asked, and we have lots of other C-language questions about finding unique elements, removing duplicates, etc. In fact, if you search for questions tagged with both [tag:c] and [tag:duplicates], you'll find (as I'm writing this) [113 questions](https://stackoverflow.com/questions/tagged/duplicates+c). The best non-brute-force solution will depend on the question, e.g.: Do you just need to detect dupes, or remove them in place, or create a new array of unique values? If you have a specific question, ask it. – Caleb Feb 06 '19 at 14:28
0

You can use this method:

// sort a copy of the array with the algorithm you like the most and then...
bool duplicates = false;
for(i = 0; i < 7; i++)
{
   if (array[i] == array[i+1])
   {
      duplicates = true;
      break;
   }
}
Aurelio De Rosa
  • 21,856
  • 8
  • 48
  • 71
  • The OP has indicated that array modifications should be avoided. Also, `$` is not a valid character in C's identifiers per the standard, although your compiler may happen to support it. Oh, and you're accessing a non-existing array element, `array[9]` when `i=8`. – Alexey Frunze Nov 20 '11 at 04:32
  • @Alex Where did you see the $? – Aurelio De Rosa Nov 20 '11 at 04:32
  • The Q says reordering the array isn't acceptable. You could copy the array first, sort the copy, and then look for duplicates using your code above, but that wouldn't tell you which indices in the original array are the duplicates. – Caleb Nov 20 '11 at 04:33
  • @Caleb The OP doesn't ask for the index. It actually just want to know if there's a duplicate. – Aurelio De Rosa Nov 20 '11 at 04:34
-6
 int main()
 {
 srand(time(0));
 int data[10];

for(int c=0;c<=9;c++)
{
    bool found = false;
    while(!found)
    {
        data[c]=rand()%10+1;
        found=true;
        for(int r=0;r<c;r++)
        {
            if(data[c]==data[r]) found=false;
        }
    }
}

for(int c=0;c<=9;c++) cout << data[c] << endl;
return 0;
}
mikered159
  • 1