Tìm số nào xuất hiện nhiều nhất trong một vector

Question

Tôi có một số số được lưu trữ trong vectơ. Tôi muốn tìm số nào xuất hiện nhiều nhất trong vectơ.

Có bất kỳ thuật toán dễ dàng/nhanh nào (STL hoặc bất kỳ thuật toán nào) thực hiện điều này không?

Answer 1

Sắp xếp, sau đó lặp lại thông qua nó và giữ một bộ đếm mà bạn tăng khi số hiện tại giống với số trước đó và đặt lại về 0 nếu không. Ngoài ra, hãy theo dõi giá trị cao nhất của bộ đếm cho đến nay và số lượng hiện tại là khi giá trị đó đạt được. Giải pháp này là O(n log n) (vì sắp xếp). Ngoài ra, bạn có thể sử dụng hashmap từ int đến int (hoặc nếu bạn biết các số nằm trong phạm vi giới hạn, bạn chỉ có thể sử dụng mảng) và lặp lại trên vectơ, tăng the_hashmap[current_number] cho 1 cho mỗi số. Sau đó lặp lại thông qua hashmap để tìm giá trị lớn nhất của nó (và khóa thuộc về nó). Điều này đòi hỏi một cơ sở dữ liệu hashmap mặc dù (trừ khi bạn có thể sử dụng mảng cũng sẽ nhanh hơn), mà không phải là một phần của STL.

Answer 2

Đây là cách tôi đã làm nó:

int max=0,mostvalue=a[0]; 
    for(i=0;i<a.size();i++) 
    { 
     co = (int)count(a.begin(), a.end(), a[i]); 
     if(co > max) 
     {  max = co; 
       mostvalue = a[i]; 
     } 
    } 

Tôi chỉ không biết nhanh như thế nào nó là, ví dụ: O()? Nếu ai đó có thể tính toán nó và đăng nó ở đây thì sẽ ổn thôi.

Answer 3

Nếu bạn muốn tránh phân loại vector của bạn v, sử dụng bản đồ:

int max = 0; 
int most_common = -1; 
map<int,int> m; 
for (vi = v.begin(); vi != v.end(); vi++) { 
    m[*vi]++; 
    if (m[*vi] > max) { 
    max = m[*vi]; 
    most_common = *vi; 
    } 
} 

Điều này đòi hỏi nhiều bộ nhớ hơn và có một thời gian chạy dự kiến ​​rất giống nhau. Bộ nhớ được yêu cầu phải theo thứ tự của bản sao vector đầy đủ, ít hơn nếu có nhiều mục trùng lặp.