벡터에서 동일한 정수의 수를 찾습니다.

Question

저는 정수의 벡터를가집니다. 벡터에서 같은 정수를 계산하고 싶습니다. 단순한 알고리즘 만 있으면됩니다. 그러나 간단한 알고리즘만으로 너무 많은 헤더 나 함수를 사용하지 않아도됩니다. 정말 고마워요 예 :

std::v={1,1,1,2,2,3} 1:3----2:2----3:1 

Answer 1

Sort을 한 다음 숫자는 다음의 모든 변경을 계산합니다.

선택 사항 : 출력 배열에 개수를 저장합니다. 후 일종의

시도 :

int count = 1; 
for(int i = 1; i < v.size(); i++) 
{ 
    if(v[i-1] == v[i]) 
    { 
     count++; 
    } 
    else 
    { 
     std::cout << v[i-1] << count << std::endl; 
     count = 0; 
    } 
} 
std::cout << v[v.size()-1] << count << std::endl; 

Answer 2

또 다른 해결책은 int로 INT에서 추가 사전을 만드는 것입니다. 벡터에서 숫자로 (키로) 숫자를 삽입하십시오. number가 있으면 해당 키의 값을 증가시켜야합니다.

참고. 이 사전 (지도)은 정수의 출현 횟수를 벡터에서 유지합니다.

지도의 머리말을 포함해야합니다.

이러한 알고리즘의 전체적인 복잡성은 O (N log N)입니다. 어쩌면 그런 알고리즘은 정렬의 사용보다 빠를 것이다. 추가 트래버스는 사용하지 않습니다. 그리고 숫자의 발생에 대한 정보를 가지고있는 구조를 가지고 있습니다.

Answer 3

가장 일반적인 솔루션은 O (n log n) 시간에 실행되며, 배열을 정렬 한 다음 계산을 반복해야합니다 @ yd1에 설명 된대로 가장 긴 실행 시간.

또 다른 방법은 해시 테이블을 사용하여 빈도 테이블을 생성하는 것입니다. 이것은 O (n) 시간 (O (1) 해시 테이블 삽입 및 검색을 가정 할 때)에서 실행되지만 해시 테이블을 설정하고 해시 테이블 (및 충돌 등)을 다시 할당해야하는 오버 헤드 때문에 작은 입력 벡터 길이에 비해 차선입니다.

해시 테이블을 사용하려면 #include <unordered_map>을 사용할 필요가 없습니다. 직접 구현하는 방법은 학부 과정입니다. :) 그러나 필요한 기능을 최소한으로 유지하려면 많은 노력을해야합니다. 당신이 벡터 값의 범위 (예 : 0 <= i < 256를) 다음지도로 배열을 사용할 수있는 몇 가지 적절한 범위 내에 있음을 보장 할 수있는 경우

그러나 :

vector<int> values = ... 

int table[256] = {0}; 
for(auto i = values.begin(); i != values.end(); ++i) { 

    assert(0 <= i && i < 256); 

    table[*i]++; 
} 

그런 얻을 table 반복 어떤 값이 같은지 :

for(size_t i = 0; i < 256; ++i) { 

    if(table[i] > 1) cout << i << " appeared " << table[i] << " times." << endl; 
}