Đếm tần suất tất cả phần tử trong mảng với O(1) không gian thêm và O(n) thời gian trong C++

Chúng ta được cho một mảng các phần tử giá trị từ 1 đến n. Một số phần tử lặp lại, một số thiếu. Mục tiêu là tìm tần suất của tất cả phần tử trong thời gian O(n) và không gian thêm O(1).

Ví dụ

Đầu vào

Arr[] = { 1, 2, 2, 3, 4, 4, 4, 5 }

Đầu ra

1 → 1, 2 → 2, 3 → 1, 4 → 3, 5 → 5

Giải thích − Phần tử lớn nhất là 5, đầu ra cho thấy số lần mỗi phần tử xuất hiện trong mảng.

Đầu vào

Arr[] = { 1, 4, 4, 5, 5, 5, 5 }

Đầu ra

1 → 1, 2 → 0, 3 → 0, 4 → 2, 5 → 4

Giải thích − Phần tử lớn nhất là 5, đầu ra cho thấy số lần mỗi phần tử xuất hiện.

Phương pháp sử dụng trong chương trình dưới đây

• Chương trình dưới đây hoạt động cho mảng số 1 đến 10.
• Hàm printfrequency(int arr[], int n) nhận mảng và kích thước n, trả về số lượng số 1 đến 10 có trong mảng.
• Làm arr[i] = arr[i] - 1 để mỗi chỉ số lưu tần suất của số i, 1 lưu tại chỉ số 0, v.v.
• Dùng vòng for tại mỗi tần suất arr[arr[i] % 10] cộng 10 vào giá trị gốc.
• Nếu số i xuất hiện x lần thì 10 sẽ được cộng x lần.
• Bây giờ dùng vòng for in tần suất bằng arr[i] / 10 cho tất cả phần tử i+1 tại chỉ số i.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

void printfrequency(int arr[], int n) { 
    int i = 0; 
    // 1 thành 0, 2 thành 1 ..... 10 thành 9 nên arr[i] sẽ có count của i
    for (i = 0; i < n; i++) 
        arr[i] = arr[i] - 1; 
    // vì số 1-10 cộng 10 vào tất cả (num%10 là chính num)
    for (i = 0; i < n; i++) 
        arr[arr[i] % 10] = arr[arr[i] % 10] + 10; 
    for (i = 0; i < 10; i++) 
        cout << i + 1 << " -> " << arr[i] / 10 << endl; 
} 

int main() { 
    int arr[] = {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printfrequency(arr, n); 
    return 0; 
}

Kết quả

1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1
6 -> 1
7 -> 3
8 -> 2
9 -> 5
10 -> 0