2 
void findodd(int a[])
{
  int hash[100];
  int i;
  int c[100]={0};
  for(i=0;i<6;i++)
  { 
    c[a[i]]=c[a[i]]+1;
    hash[a[i]]=c[a[i]];
    if(c[a[i]]%2==0)
      hash[a[i]]=0;
  }
  for(i=0;i<6;i++)
    if(hash[a[i]]!=0)
      cout<<a[i];
}
int main()
{
  int a[] = {1,3,3,5,5,5};
  findodd(a);
  return 0;
}

プログラムは、配列内で奇数回出現する整数を見つけることです。上記のプログラムへのリンクは次のとおりです。

4

3 に答える 3

2

アルゴリズムがすでにO（n）で実行されていることを考えると、出力内の重複するエントリを消去しようとしていると思います。考えられる解決策の1つは次のとおりです。

void findodd(int a[])
{
  int hash[100];
  int i;
  int c[100]={0};

  int hashdup[100];
  memset(hashdup, 0, sizeof(int)*100);

  for(i=0;i<6;i++)
  { 
    c[a[i]]=c[a[i]]+1;
    hash[a[i]]=c[a[i]];
    if(c[a[i]]%2==0)
      hash[a[i]]=0;
  }
  for(i=0;i<6;i++)
  {
    if(hash[a[i]]!=0)
      hashdup[a[i]]++;
    if (hashdup[a[i]]==1)
      cout<<a[i];
  }
}
于 2011-03-13T21:12:51.520 に答える
1 
#include <iostream>

void find_odd(int a[])
{
    int hash[101] = { 0 };
    int i;
    for( i = 0 ; i < 6 ; i++ )
    { 
        hash[ a[i] ]++;
    }

    for(i=0 ; i<100 ; i++)
        if(hash[i] != 0 && !(hash[i] % 2 == 0))
            std::cout << i << std::endl;    
}

int main()
{
    int a[] = {1,3,3,5,5,5};
    find_odd(a);
    return 0;
}

std::vectorただし、および/またはを使用する方がよい場合がありますstd::map。

ネガ付き：ただし、-100->+100の範囲のみ。負の配列インデックスを持つことはできないので+100、すべてに対して、hash0から200までの配列を使用します。

#include <iostream>

void find_odd(int a[])
{
    int hash[201] = { 0 };
    int i;
    for( i = 0 ; i < 9 ; i++ )
    { 
        hash[ a[i]+100 ]++;
    }

    for(i=0 ; i<201 ; i++)
        if(hash[i] != 0 && !(hash[i] % 2 == 0))
            std::cout << i-100 << std::endl;    
}

int main()
{
    int a[] = {-1 , -1 , -1 , 1 , 3 , 3 , 5 , 5 , 5};
    find_odd(a);
    return 0;
}

std::vectorおよびstd::map（正の数と負の数の両方で機能します）

#include <iostream>
#include <map>
#include <vector>

void find_odd_mapped(std::vector<int>& a)
{
    std::map<int , int> hash;
    std::map<int , int>::iterator map_iter;
    std::vector<int>::iterator vec_iter;

    for( vec_iter = a.begin() ; vec_iter != a.end() ; ++vec_iter )
        ++hash[*vec_iter];


    for(map_iter = hash.begin() ; map_iter != hash.end() ; ++map_iter)
        if(!((*map_iter).second % 2 == 0))
            std::cout << (*map_iter).first << std::endl;
}

int main()
{
    std::vector<int> a;
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(1);
    a.push_back(3);
    a.push_back(3);
    a.push_back(5);
    a.push_back(5);
    a.push_back(5);
    find_odd_mapped(a);
    return 0;
}
于 2011-03-13T21:16:08.947 に答える
0

唯一のポイントは、エントリの境界を知っているかどうか、入力の種類が限られている場合は上記のすべてのコードが機能しますが、境界がわからない場合、または境界が高すぎる場合（たとえば、エントリの整数範囲）、最良のアルゴリズムでさえ、重複するエントリを削除するためにO（nlogn）を使用します。

于 2011-03-13T21:49:08.540 に答える