1

n個の要素が同じで残りのn個の要素がすべて異なる2n個の要素を持つ配列があります。この問題を解決するための複雑なアルゴリズムは他にもたくさんあります。

質問：このアプローチでも同じ結果が得られますか、それともどこかで間違っていますか？

#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]場合は、解決策が存在するかどうかに違いありません。

多数決要素の問題に対する 1 つの解決策は、多数決候補要素に遭遇するたびにカウンターをカウントアップし、候補とは異なる数に遭遇したときにカウンターをカウントダウンする配列をスキャンすることです。カウンターが 0 の場合、次の要素が自動的に新しい候補と見なされます。

スキャンの終了時にカウンターが正の場合、候補はアレイの別のスキャンでチェックされます。カウンターが 0 の場合、または 2 回目のスキャンが失敗した場合、多数決要素はありません。

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 に答える