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을 음의 배열 인덱스를 가지고 200

std::vector와

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

0에서 hash 배열을 질수

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 항목을 제거합니다.