Trung vị và Mode bằng Counting Sort trong C++

Tìm Median (trung vị) và Mode (mốt) của mảng dùng Counting Sort, phù hợp khi giá trị phần tử trong phạm vi giới hạn. Ví dụ {1, 1, 1, 2, 7, 1} → Mode = 1, Median = 1.5.

• Median: phần tử giữa khi sắp xếp (n lẻ) hoặc trung bình 2 phần tử giữa (n chẵn).
• Mode: phần tử xuất hiện nhiều nhất.

Các bước: tạo mảng đếm, tìm chỉ số có đếm lớn nhất → Mode. Tiếp tục counting sort để có mảng đã sắp xếp, lấy Median.

Lưu ý: Code mẫu gốc bị trùng với bài toán khác. Dưới đây là code đúng cho Median/Mode bằng Counting Sort:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void medianAndMode(vector<int> arr) {
    int n = arr.size();
    if (n == 0) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    vector<int> count(range, 0);
    for (int x : arr) count[x - minVal]++;
    // Mode
    int mode = minVal, maxCount = 0;
    for (int i = 0; i < range; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
            mode = i + minVal;
        }
    }
    // Counting sort để lấy mảng sorted
    vector<int> sorted;
    for (int i = 0; i < range; i++)
        for (int c = 0; c < count[i]; c++)
            sorted.push_back(i + minVal);
    // Median
    double median;
    if (n % 2 == 1)
        median = sorted[n/2];
    else
        median = (sorted[n/2 - 1] + sorted[n/2]) / 2.0;
    cout << "Mode: " << mode << ", Median: " << median;
}

int main() {
    vector<int> arr = {1, 1, 1, 2, 7, 1};
    medianAndMode(arr);
}

Kết quả

Mode: 1, Median: 1.5