查找在2n大小数组中重复n次的元素.这个解决方案有效吗？

Question

我有一个有2n个元素的数组,其中n个元素相同,剩下的n个元素都是不同的.还有很多其他复杂的算法可以解决这个问题.

问题:这种方法是否会产生相同的结果,或者我在某处出错？

#include<stdio.h>

main()
{
    int arr[10],i,res,count=0;
    printf("Enter the array elements:\t");
        for(i=0;i<10;i++)
    scanf("%d",&arr[i]);
    for(i=0;i<8;i++)
    {
        if(arr[i]==arr[i+1] || arr[i]==arr[i+2])
         {
             res=arr[i];
             break;
         }
        else if(arr[i+1]==arr[i+2])
        {
            res=arr[i+1];
            break;
        }
    }
    for(i=0;i<10;i++)
        if(arr[i]==res)
           count++;
    if(count==5)
        printf("true, no. repeated is:\t%d",res); 
    else printf("false");    
    return 0;
}

Answer 1

除了琐碎的2元素情况失败之外,在这种情况下它也失败了4个元素:

a b c a

我认为解决这个问题的最简单方法是解决多数元素问题a[1] ... a[2*N-1],如果没有找到多数,那么必须a[0]存在一个解决方案.

多数元素问题的一个解决方案是在遇到多数候选元素时扫描数组计数计数器,并在遇到与候选不同的数字时对计数器进行倒计时.当计数器为0时,下一个元素自动被视为新候选者.

如果在扫描结束时计数器为正,则通过阵列上的另一次扫描检查候选者.如果计数器为0,或第二次扫描失败,则没有多数元素.

int majority (int a[], int sz) {
  int i, count1 = 0, count2 = 0;
  int candidate = -1;
  for (i = 0; i < sz; ++i) {
    if (count1 == 0) candidate = i;
    count1 += ((a[candidate] == a[i]) ? 1 : -1);
  }
  if (count1 > 0) {
    for (i = 0; i < sz; ++i)
      count2 += (a[candidate] == a[i]);
  }
  if (count2 <= sz/2) candidate = -1;
  return candidate;
}