1

我有一个包含 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;
}
4

2 回答 2

6

除了简单的 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;
}
于 2012-07-13T05:33:43.943 回答
1

当数组只有 2 个元素时，您的算法将失败。它不处理琐碎的情况

于 2012-07-13T05:23:10.333 回答