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) 上运行，我假设您正在寻找删除输出中的重复条目。一种可能的解决方案是：

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对所有人来说，hash数组从 0 到 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::vectorand 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 回答