如何從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

#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 hash陣列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; 
} 

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

Answer 3

唯一的一點是，如果您知道輸入或不輸入邊界，如果輸入的輸入類型有限，那麼上面的所有代碼都可以工作，但是如果您不知道邊界或邊界是否太高（對於例如你哈有一個整數範圍的條目），那麼即使最好的算法使用O（nlogn）來刪除dublicate條目。