c - C中递归查找数组中重复条目的方法

Question

我正在尝试编写一个递归函数来查找整数数组中的重复项。例如，如果数组为:{4, 1, 4, 3, 2, 3}，则应返回 2。我尝试了类似合并排序的方法，但没有成功。有人可以帮忙吗？

我的尝试(仅适用于有序数组):

int count(int arr[], int bot, int top){
  if(bot==top) return 0;
  else{
    int med = (bot+top)/2;
    int n = count(arr, bot, med) + count(arr, med+1, top);
    if(arr[med]==arr[med+1]) n++;
    return n;
  }
}

Answer 1

您只是检查是否arr[med]==arr[med+1]，当您遇到像 111 这样的情况时，就会出现问题，那么计数将变为 2，但计数实际上应该成为一体。因此添加一个额外的标志来检查相同的元素是否重复。

对数组进行排序。也许您可以使用合并排序或其他方法来执行此操作，然后类似的操作应该可以工作!

#include <stdio.h>

int main(void) {
    // your code goes here
    int a[16] = {1,1,1,1,1,1,1,1,1,1,1,2,2,3,3,5};
    int out = count(a,0,15);
    printf("%d\n",out);
    return 0;
}

int count(int arr[], int bot, int top){
  int flag = 0;
  if(bot==top) return 0;

  else{
    int med = (bot+top)/2;
    int n = count(arr, bot, med) + count(arr, med+1, top);
    if(arr[med]==arr[med+1])
    {
        flag = arr[med-1];
        if(flag != arr[med])
            n++;
    }
    return n;

    }
}