c++ - 如何在 O(n) 运行时间内从答案中删除重复项？

Question

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;
}

该程序是找出数组中出现奇数次的整数。这是link到上面的程序。

Answer 1

鉴于您的算法已经在 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];
  }
}