使用C语言查找数组中重复元素的数量

Question

我无法找到正确的逻辑来查找数组中重复元素的数量。我能理解为什么我的逻辑不起作用，但是我无法克服它。

以下是实际问题:

编写一个程序，声明一个大小为n的整数数组arr。先从用户处获取一个正整数n，然后读取n个数字并将它们存储在arr中。检查并打印arr中重复的数量。结果是数组中所有重复数字的总和。
例如: 如果arr = [4,3,4,4,3,4,5]
那么重复的次数是6（其中有4个重复的数字4和2个重复的数字3）

以下是代码:

#include <stdio.h>

int main() {
    int n, i, j, count = 1, p = 0;
    printf("Enter the length of array");
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i++) {
        printf("Enter a number\n");
        scanf("%d", &arr[i]);
    }
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;
                break;
            }
        }
        if (count != 1) {
            p = p + count;
            count = 1;
        }     
    }
    printf("Number of repetitions are %d", p);
}

对于上述代码，如果我们将数组按照问题中提到的方式进行处理，每当我的代码遇到两个相同的数字4时，它都会将它们都计算在内，因此我的程序最终会多计算一些4。所以我无法找到更好的逻辑来解决这个问题。
(我是初学者，不太了解C语言中使用的高级函数/方法)

- sameed hussain

---

break 的逻辑是什么？ - Damien

计算数组元素频率的逻辑是创建另一个数组。初始化新数组[new_array] [value] = 1。使用值作为新数组中的索引，然后像这样递增new_array [value] ++。 - Arun Sharma

Answer 1

你可以做的一件事是，为你检查过的数字保留一个额外的数组，并且每次比较数字时都要检查你是否已经见过此数字。

我还想介绍另一种解决这个问题的方法。如果我们知道列表中的数字不会太大，我们可以使用一个数组来跟踪计数。

//numbers = {4, 3, 4, 4, 3, 4, 5}
int max = findMaxValue(numbers);
int counts[max]; //should be done with dynamic memory allocation
for(i=0;i<max;i++){
    counts[max] = 0;
}
for(i=0;i<numbers.size;i++){
    counts[numbers[i]]++;
}
int sum = 0;
for(i=0;i<max;i++){
    if(counts[i] > 1){
        sum += counts[i];
    }
}

另一件可以做的事情是，先对数字进行排序，然后比较相邻元素。

- Metin Usta

---

感谢您提供另一种解决问题的方法。 - sameed hussain

你的方法没有考虑负数，如果数组中的某个值足够大，会导致堆栈溢出！ - chqrlie

Answer 2

我认为首先通过对相同元素进行排序将它们放在一起是一个好主意。

#include<stdio.h>

int main() {
    int n = 0, count = 0;

    printf("Enter the length of array: ");
    scanf("%d", &n);

    int arr[n];

    for (int i = 0; i < n; i++) {
        printf("Enter a number: ");
        scanf("%d", &arr[i]);
    }

    //sort
    for (int j = 0; j < n - 1; j++) {
        for (int k = j + 1; k < n; k++) {
            if (arr[j] >= arr[k]) {
                arr[j] = arr[j] ^ arr[k];
                arr[k] = arr[j] ^ arr[k];
                arr[j] = arr[j] ^ arr[k];
            }
        }
    }

    // count
    int num = 1; // If you don’t want to include the repeated number itself, replace all "num = 1" with "num = 0"
    for (int j = 0; j < n - 1; j++) {
        if (arr[j] == arr[j + 1]) num++;
        else {
            printf("The num %d repeats %d times\n", arr[j], num); // You can delete this line
            count += num;
            num = 1; //Initialize num to avoid repeated accumulation of num and prepare to enter the next loop
        }
    }
    printf("Total repeats: %d\n", count);
    
    return 0;
}

- hui-shao

---

谢谢您提供解决问题的另一种方法。 - sameed hussain

你应该添加一个测试来避免计算非重复项：if (num > 1) count += num; - chqrlie

Answer 3

为避免重复计数，您需要跟踪已经重复出现的数字。我建议使用第二个数组来保存“已经重复”的值：

#include <stdio.h>

int main()
{
    int n, p = 0, r = 0;

    printf("Enter the size of the array: ");
    scanf(" %u",&n);
    int arr[n];
    int rep[n - 1];
    for (int i = 0; i < n; i++) {
        printf("Enter arr[%d]: ",i);
        scanf(" %d",&arr[i]);
    }
    for (int i = 0; i < n; i++) {
        int count = 1, j;
        for (j = 0; j < r; j++) {
            if (arr[i] == rep[j])
                break;
        }
        if (j < r)
            continue;
        for (j = i + 1; j < n; j++)
            if (arr[i] == arr[j])
                count++;
        if (count > 1) {
            p = p + count;
            rep[r++] = arr[i];
        }     
    }
    printf("Number of repitions is %d\n",p);
}

- SGeorgiades

---

有趣的方法，但与暴力方法相同的复杂度并且使用了两倍的空间。只有在存在大量相同值的情况下才能节省时间。 - chqrlie

@SGeorgiades，我想澄清一下你为什么要声明数组rep的长度为(n-1)，因为代码在长度为n时也能正常工作。 - sameed hussain

@SGeorgiades 你好，能否解释一下为什么要使用%u而不是%d？ - sameed hussain

我使用了n - 1，因为重复次数必须少于数组中的元素个数。我想我也可以使用n / 2同样有效。 - SGeorgiades

由于问题要求 n 必须为正数，因此 %u 可以确保不会输入负数。 - SGeorgiades

Answer 4

让我教你如何处理这样的问题，通过在源代码中添加几行代码：

#include <stdio.h>
int main()
{
    int n,i,j,count=1,p=0;
    printf("Enter the length of array");
    scanf("%d",&n);
    int arr[n];
    for(i=0;i<n;i++)
    {
        printf("Enter a number\n");
        scanf("%d",&arr[i]);
    }
    for(i=0;i<n;i++)
    {
        printf("Start for-loop for i, i=[%d]",i);
        for(j=i+1;j<n;j++)
        {
            printf("  Start for-loop for j, j=[%d]", j);
            if(arr[i]==arr[j])
            {
                printf("    Both arr[%d] and arr[%d] equal [%d]", i, j, arr[i]);
                count++;
                printf("      As a result, count=[%d], p=[%d]", count, p);
                break;
            }
            else printf("    Arr[%d]<>arr[%d]: arr[i]=%d, arr[j]=%d, count=[%d], p=[%d]", i, j, arr[i], arr[j], count, p);
        }
        if(count!=1)
        {
            printf("  count=[%d] which is different than 1 while p=[%d]", count, p);
            p=p+count;
            printf("  p has been increased by count and now, p=[%d]", p);
            count=1;
            printf("  count is brought back to 1");
        }     
    }
    printf("Number of repitions are %d",p);

}

JEZUS？所有这些printf()命令？
是的：作为一个初学者，你最好放置太多的这样的命令，而不是太少。一个重要的事情：不要只读取输出并从那里开始，而是首先尝试想象您期望的输出应该是什么样子。这样，您将立即看到您的期望与实际结果不符，并且您将知道您做错了什么。

...还有一个重要的注意事项：一旦完成，请勿删除这些printf()行，而是将它们放入注释中。如果您需要根据更改的要求调整代码，您可能需要再次使用这些printf()行。

- Dominique

Answer 5

你的思路是对的，但是逻辑有误：你没有计算每个重复值的最后一个元素。

• 你应该将count初始化为0而不是1
• 你应该从0开始迭代内部循环，而不是从i+1开始，以计算arr[i]的出现次数，并继续遍历整个数组，删除break语句。
• 如果count不等于1，即元素重复，则只需增加p。

这种方法的时间复杂度与你的方法相同，为O(N²)。通过对数组进行排序并在单次扫描中计算重复项，可以将复杂度降低到O(N.log(N))。

甚至更有效的方法可能达到线性时间复杂度：使用哈希表，您将计算从用户读取的每个元素的出现次数。然后，您将枚举哈希表，计算非零计数的数量。

以下是修改后的版本：

#include <stdio.h>

int main() {
    int n, i, j, p = 0;

    printf("Enter the length of array: ");
    if (scanf("%d", &n) != 1)
        return 1;

    int arr[n];

    for (i = 0; i < n; i++) {
        printf("Enter a number: ");
        if (scanf("%d", &arr[i]) != 1)
            return 1;
    }
    for (i = 0; i < n; i++) {
        int count = 0;
        for (j = 0; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;
            }
        }
        if (count != 1) {
            p = p + 1;
        }     
    }
    printf("Number of repetitions: %d\n", p);
    return 0;
}

- chqrlie