0

我必须编写一个程序来查找数组中的重复项以及每个重复项在数组中出现的次数。这是我的代码：

#include <stdio.h>
#include <stdlib.h>

#define DIM 5

int contains (int v[], int dim, int n);

int main(int argc, char** argv) 
{
    int i, j, k = 0, found;
    int v[DIM];
    int dup[DIM] = {0};

    for (i = 0; i < DIM; i++)
    {
        printf("Insert element in the array: ");
        scanf("%d", &v[i]);
    }

    for (i = 0; i < DIM; i++)
    {
        found = 0;

        if (contains (dup, DIM, v[i]) == 0)
        {
            for (j = 0; j < DIM; j++)
            {
                if (v[i] == v[j] && (i != j))
                {
                    found ++;
                    dup[k] = v[i];
                    k++;
                }
            }
            if (found != 0)
            {
                printf("Element %d has been repeated %d times\n", v[i], found);
            }
        }
    }


    return (0);
}


int contains (int v[], int dim, int n)
{
    int i;
    int found = 0;

    for (i = 0; i < dim; i++)
    {
        if (v[i] == n)
        {
            found = 1;
        }
    }

    return found;
}

该程序运行良好，但我认为它不是很有效。当然，它存在一种让程序高效的方法，不是吗？我的意思是一种继续使用数组而不是任何其他结构的方法

4

4 回答 4

1

一个好的哈希表可以在线性时间内解决这个问题。如果你不想搞砸数据结构，那么这里有一个 O(n lg n) 的类似 C 伪代码的解决方案：

// given: an array a of n integers

sort(a, n);

for (int i = 0;;) {
    int value = a[i];
    int count = 0;

    do {
        i++;
        count++;
    } while (i < n && a[i] == value);

    if (count > 1)
        printf("Element %d has been repeated %d times\n", value, count);
}

排序可以用qsort. 该算法的其余部分依赖于这样一个事实，即在排序后，所有重复项将被分组在一起。

于 2013-08-08T09:29:14.007 回答
0

如果你知道用户输入的数字范围，这里有一个 O(n) 方法。假设您知道这些数字将在 0-99 的范围内。

这是一个伪代码。

//Input the array elements in an array named arr[]

static int freq[101]; //create a static array to initialize all elements to 0

//scan the array arr and increment the counter at index of freq array

for(int i=0;i<(arr.length);i++)
    freq[arr[i]]++;

//Now scan the array named freq and print the frequency of each of the numbers.
for(int i=0;i<101;i++)
    if(freq[i]>0)
         printf("Frequency of %d is:- %d ",i,freq[i]);

我希望这可以帮助你。

于 2013-08-08T10:28:17.850 回答
0

您应该在填充数组时对数组进行排序（以 qsort 为例），使用二分搜索查找您的数字，然后从其索引中搜索是否有重复项：

array:
0 1 2 5 7 7 48 48 56 72

您正在7通过示例进行搜索。通过二分法搜索，您可以找到7复杂度为 O(log n) 的 a。我们称它的索引为 IDX（在本例中等于 5）

大批：

0 1 2 5 7 7 48 48 56 72 103
          ^
          |
         IDX(=5)

现在你只需要像这样循环：

int count = 0;
int idx = 5; // must be finded via a dichotomic search
int toFind = array[idx];

    while (idx >= 0 && array[idx] == toFind)
    {
       ++count;
       --idx;
    }
    idx = 5:
    while (idx < arrayLength)
    {
       ++count;
       ++idx;
    }

仅当您可以对数组进行排序并且要避免使用哈希表时，此解决方案才有效。

于 2013-08-08T09:30:10.840 回答
-1 
#include<stdio.h>
#include<conio.h>
void main()
{
  int i,j,a[5];

  clrscr();

  printf( "Enter the element in array\n" );
  for( i=0; i<5; i++ ) {
    scanf( "%d", &a[i] );
  }
  for(i=0;i<5;i++) {
    for(j=i+1;j<5;j++) {
      if(a[j]==a[i])
        printf("Repeated value is %d",a[i]);
    }
  }

  getch();
}
于 2015-05-20T20:29:14.143 回答