如何检查数组中是否有重复项？

Question

我正在将文件内容读入一个9个元素的数组中。我需要检查这个数组中是否有重复项。我需要在不重新排序或更改数组任何内容的情况下完成这个任务。

我应该如何处理？

- Petefic

---

可能是重复的 从指针数组中查找重复项 - Pubby

Answer 1

用暴力破解的方法。

由于该数组只有9个元素，所以最多只需进行36次比较就可以找到任何重复项：

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
        }
    }
}

- Caleb

---

你说的 sizeof(array) 当然是指 sizeof(array) / sizeof(array[0]) 吧？ - Alexey Frunze

第一个和外部循环只需要执行到 count - 1，否则在最后一次迭代时内部循环完全无用。我会编辑答案以反映这个改进。 - nbro

我很好奇，几乎无法想象你是如何计算比较次数的@Caleb。如果您有时间，能否稍微详细解释一下？我很感兴趣并且忘记了实际的方法。谢谢。 - AT-2017

假设你有一个包含9个项目的数组，想要比较每一对项目：从第一个项目开始，将其与数组中的另外8个项目进行比较。这样就需要进行8次比较。然后移动到第二个项目。不需要将其与第一个项目进行比较，因为已经比较过了，所以将其与剩下的7个项目进行比较。重复此过程，最终会得到8+7+6+5+4+3+2+1=36次比较。这正是上述代码所做的。 - Caleb

@jangorecki 我可以这样做，但那样我就回答了与OP提出的问题不同的问题，而我们有很多其他关于查找唯一元素、删除重复项等C语言问题。实际上，如果您搜索同时标记为[tag:c]和[tag:duplicates]的问题，您将会发现（在我撰写本文时）113个问题。最好的非蛮力解决方案将取决于问题，例如：您只需要检测重复项，还是在原地删除它们，还是创建一个新的唯一值数组？如果您有具体问题，请提出。 - Caleb

Answer 2

你可以使用这个方法：

// 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

---

OP已经指出应该避免对数组进行修改。此外，根据标准，$不是C标识符中的有效字符，尽管您的编译器可能支持它。哦，当i=8时，您正在访问一个不存在的数组元素array[9]。 - Alexey Frunze

@Alex 你在哪里看到了 $ 符号？ - Aurelio De Rosa

Q说重新排序数组是不可接受的。你可以先复制数组，对副本进行排序，然后使用上面的代码查找重复项，但这并不能告诉你原始数组中哪些索引是重复的。 - Caleb

@Caleb，OP并没有要求索引。实际上，它只是想知道是否存在重复项。 - Aurelio De Rosa

Answer 3

 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