如何在 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;
}

该程序的目的是找出数组中出现奇数次的整数。这是上述程序的链接。

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

Answer 2

#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 并使用从 0 到 200 的 hash 数组。

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

Answer 3

唯一的一点是您是否知道条目的边界，如果输入类型有限，那么上面的所有代码都可以工作，但是如果您不知道边界或者边界太高（例如您有整数范围的条目），那么即使最好的算法也使用 O(nlogn) 来删除重复的条目。