查找数组中的重复项数

Question

我有一个数组，比如说 1,3,3,1,2 代码的输出必须是 4（2 次重复 1 + 2 次重复 3=4）。我怎么能在 C 中做到这一点？这是我的尝试。

#include <stdio.h>
int main(){
int n,i,j,temp;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++){
  scanf("%d",&arr[i]);
}
for(i=0;i<n;i++){
  int min = i;
  for(j=i+1;j<n;j++){
    if(arr[j]<arr[min]) min=j;
  }
  temp= arr[min];
  arr[min]=arr[i];
  arr[i]=temp;
  
}
  int count=1;
  for(i=0;i<n;i++){
    if(arr[i]==arr[i+1])count++;
    else continue;
  }
  printf("%d",count);
}

Answer 1

看起来你的循环有几个问题。

索引超出数组末尾，这是未定义的行为
不明白何时计算一组重复项中的第一项

关于#1，最好从 1 而不是 0 开始循环，然后检查索引 i-1 与 i.

关于#2，您的代码有效，但仅当只有一个数字重复时才有效。这是因为您从 1 开始计数。但是，当您遇到另一组时，该假设就会失效。最简单的方法就是只记录你是否开始一个新组。

让我们把这些放在一起：

int count = 0;
int first = 1;
for(i = 1; i < n; i++) {
    if (arr[i-1] == arr[i]) {
        count += first + 1;
        first = 0;
    } else {
        first = 1;
    }
}

至于排序步骤，它使用的算法效率极低。这对于小型数据集很好，但如果您有大量输入，就会遇到问题。明智的做法是使用 qsort 之类的东西。有很多关于如何执行此操作的示例。

所以，你现在的运行时间是 O(N^2)。使用快速排序，它变为 O(N.logN).

您可以使用哈希 table 之类的东西进一步减少运行时间，它只存储您找到的每个值的数量，并在它们到达时更新。

如果您的数据范围 well-defined 并且足够小，您可能还会受益于使用大数组而不是散列 table 并为每个可能的数字存储一个位来表示一个数字被看到。实际上，对于您的情况，由于“组中第一”问题，您需要其中两个。现在，每个到达的数字都会设置“已看到”位。如果已经看到，则设置“重复”位并增加计数。如果未设置“重复”位，则增加计数。现在你几乎可以保证 blazing-fast O(N) 运行时间，其中测试和计算重复值是 O(1)。

Answer 2

你需要的是改变这个for循环。

int count=1;
for(i=0;i<n;i++){
  if(arr[i]==arr[i+1])count++;
  else continue;
}

例如可以通过以下方式查找

int count = 0;

for ( i = 0; i < n; )
{
    int j = i;
    while ( ++i < n && arr[i-1] == arr[i] );

    if ( !( i - j < 2 ) ) count += i - j;
}

查找数组中的重复项数

Finding Number of duplicates in an array

c

arrays

for-loop

counting

duplicates