Thuật toán để tính toán chế độ

Question

Tôi đang cố gắng đưa ra một thuật toán dưới dạng một hàm chấp nhận hai tham số, một mảng và kích thước của mảng. Tôi muốn nó trả về chế độ của mảng và nếu có nhiều chế độ, hãy trả về giá trị trung bình của chúng. Chiến lược của tôi là lấy mảng và đầu tiên sắp xếp nó. Sau đó đếm tất cả các lần xuất hiện của một số. trong khi con số đó xảy ra, hãy thêm một số để đếm và lưu số đó trong một mảng m. Vì vậy, m đang giữ tất cả các số đếm và một mảng q khác đang giữ giá trị cuối cùng mà chúng ta so sánh.

Ví dụ: là danh sách của tôi là {1, 1, 1, 1, 2, 2, 2} sau đó tôi sẽ phải m[0] = 4 q[0] = 1 and then m[1] = 3 and q[1] = 2.

để chế độ là q[0] = 1;

tiếc là tôi đã không thành công cho đến nay. hy vọng ai đó có thể giúp đỡ.

float mode(int x[],int n) 
{ 
    //Copy array and sort it 
    int y[n], temp, k = 0, counter = 0, m[n], q[n]; 

    for(int i = 0; i < n; i++) 
     y[i] = x[i]; 

    for(int pass = 0; pass < n - 1; pass++) 
     for(int pos = 0; pos < n; pos++) 
      if(y[pass] > y[pos]) { 
       temp = y[pass]; 
       y[pass] = y[pos]; 
       y[pos] = temp; 
      } 

    for(int i = 0; i < n;){ 
     for(int j = 0; j < n; j++){ 
      while(y[i] == y[j]) { 
       counter++; 
       i++; 
      } 
     } 
     m[k] = counter; 
     q[k] = y[i]; 
     i--; //i should be 1 less since it is referring to an array subscript 
     k++; 
     counter = 0; 
    } 

} 

Answer 1

Mặc dù bạn có một số câu trả lời tốt rồi, tôi quyết định gửi khác. Tôi không chắc nó có thực sự bổ sung thêm nhiều thứ mới hay không, nhưng tôi hoàn toàn không chắc chắn nó cũng vậy. Nếu không có gì khác, tôi chắc chắn nó sử dụng tiêu đề tiêu chuẩn hơn bất kỳ câu trả lời nào khác. :-)

#include <vector> 
#include <algorithm> 
#include <unordered_map> 
#include <map> 
#include <iostream> 
#include <utility> 
#include <functional> 
#include <numeric> 

int main() { 
    std::vector<int> inputs{ 1, 1, 1, 1, 2, 2, 2 }; 

    std::unordered_map<int, size_t> counts; 
    for (int i : inputs) 
     ++counts[i]; 

    std::multimap<size_t, int, std::greater<size_t> > inv; 
    for (auto p : counts) 
     inv.insert(std::make_pair(p.second, p.first)); 

    auto e = inv.upper_bound(inv.begin()->first); 

    double sum = std::accumulate(inv.begin(), 
     e, 
     0.0, 
     [](double a, std::pair<size_t, int> const &b) {return a + b.second; }); 

    std::cout << sum/std::distance(inv.begin(), e); 
} 

So với @ câu trả lời Dietmar, điều này cần được nhanh hơn nếu bạn có nhiều sự lặp lại trong các con số, nhưng ý chí của ông có thể được nhanh hơn nếu các con số là chủ yếu độc đáo.

Answer 2

Đây là phiên bản làm việc của mã của bạn. m lưu trữ các giá trị trong mảng và q lưu trữ số đếm của chúng. Cuối cùng nó chạy qua tất cả các giá trị để có được số lượng tối đa, tổng của các chế độ và số lượng các chế độ riêng biệt.

float mode(int x[],int n) 
{ 
    //Copy array and sort it 
    int y[n], temp, j = 0, k = 0, m[n], q[n]; 

    for(int i = 0; i < n; i++) 
     y[i] = x[i]; 

    for(int pass = 0; pass < n - 1; pass++) 
     for(int pos = 0; pos < n; pos++) 
      if(y[pass] > y[pos]) { 
       temp = y[pass]; 
       y[pass] = y[pos]; 
       y[pos] = temp; 
      } 

    for(int i = 0; i < n;){ 
     j = i; 
     while (y[j] == y[i]) { 
      j++; 
     } 
     m[k] = y[i]; 
     q[k] = j - i; 
     k++; 
     i = j; 
    } 

    int max = 0; 
    int modes_count = 0; 
    int modes_sum = 0; 
    for (int i=0; i < k; i++) { 
     if (q[i] > max) { 
      max = q[i]; 
      modes_count = 1; 
      modes_sum = m[i]; 
     } else if (q[i] == max) { 
      modes_count += 1; 
      modes_sum += m[i]; 
     } 
    } 

    return modes_sum/modes_count; 
} 

Answer 3

Nếu bạn chỉ muốn đếm số lần xuất hiện sau đó tôi đề nghị bạn sử dụng một std::map hoặc std::unordered_map.

Nếu bạn đang lập bản đồ bộ đếm cho từng giá trị khác nhau, thì việc đếm số lần xuất hiện bằng cách sử dụng std::map là dễ dàng vì mỗi khóa chỉ có thể được chèn một lần. Để liệt kê các số riêng biệt trong danh sách của bạn, chỉ cần lặp qua bản đồ.

Dưới đây là một ví dụ về cách bạn có thể làm điều đó:

#include <cstddef> 
#include <map> 
#include <algorithm> 
#include <iostream> 

std::map<int, int> getOccurences(const int arr[], const std::size_t len) { 
    std::map<int, int> m; 
    for (std::size_t i = 0; i != len; ++i) { 
     m[arr[i]]++; 
    } 
    return m; 
} 

int main() { 
    int list[7]{1, 1, 1, 1, 2, 2, 2}; 
    auto occurences = getOccurences(list, 7); 
    for (auto e : occurences) { 
     std::cout << "Number " << e.first << " occurs "; 
     std::cout << e.second << " times" << std::endl; 
    } 
    auto average = std::accumulate(std::begin(list), std::end(list), 0.0)/7; 
    std::cout << "Average is " << average << std::endl; 
} 

Output:

Number 1 occurs 4 times 
Number 2 occurs 3 times 
Average is 1.42857 

Answer 4

Dựa trên những nhận xét, có vẻ như bạn cần phải tìm các giá trị đó xảy ra thường xuyên nhất và nếu có là nhiều giá trị xuất hiện cùng một lượng thời gian, bạn cần tạo ra mức trung bình của các giá trị này. Có vẻ như, điều này có thể dễ dàng được thực hiện bằng std::sort() sau bởi một phát hiện traversal nơi các giá trị thay đổi và giữ một vài đếm chạy:

template <int Size> 
double mode(int const (&x)[Size]) { 
    std::vector<int> tmp(x, x + Size); 
    std::sort(tmp.begin(), tmp.end()); 
    int size(0); // size of the largest set so far 
    int count(0); // number of largest sets 
    double sum(0); // sum of largest sets 
    for (auto it(tmp.begin()); it != tmp.end();) { 
     auto end(std::upper_bound(it, tmp.end(), *it)); 
     if (size == std::distance(it, end)) { 
      sum += *it; 
      ++count; 
     } 
     else if (size < std::distance(it, end)) { 
      size = std::distance(it, end); 
      sum = *it; 
      count = 1; 
     } 
     it = end; 
    } 
    return sum/count; 
}