CTDL và giải thuật - Đếm tần số (số lần xuất hiện) của các số trong dãy

Bài tập.

Nhập và một số nguyên dương n, tiếp theo là n số nguyên lần lượt là các phần tử của một dãy số, hãy đếm tần số (số lần xuất hiện) của các số trong dãy và in nó ra màn hình dưới dạng sau: "a1 t1; a2 t2; ... an tn; ", trong đó t1 là số lần xuất hiện của số a1t2 là số lần xuất hiện của a2, ... a1, a2, .. an không trùng nhau và được sắp xếp tăng dần (xem ví dụ để rõ hơn).

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    7
    -3 -3 2 4 2 2 6

    -3 2; 2 3; 4 1; 6 1;

    Với a = [-3, -3, 2, 4, 2, 2, 6] thì kết quả mong muốn là: "-3 2; 2 3; 4 1; 6 1; ".
     
  • Test mẫu 2:
     
    Input Output

    3

    999999999 999999999 999999999

    999999999 3

    Với a = [999999999, 999999999, 999999999] thì kết quả mong muốn là: "999999999 3; ".

Hướng dẫn bài tập.

Sắp xếp dãy a thành dãy không giảm để dễ dàng đếm hơn.
Hãy so sánh những phần tử kể nhau:

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

void quickSort(int a[], int l, int r){
	int p = a[(l+r)/2];
	int i = l, j = r;
	while (i < j){
		while (a[i] < p){
			i++;
		}
		while (a[j] > p){
			j--;
		}
		if (i <= j){
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j--;
		}
	}
	if (i < r){
		quickSort(a, i, r);
	}
	if (l < j){
		quickSort(a, l, j);
	}
}
int a[100001];
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    quickSort(a, 0, n-1);
    int count = 1;
    for (int i = 1; i < n; i++){
        if (a[i] == a[i-1]){
            count++;
        } else {
            cout << a[i-1] << " " << count << "; ";
            count = 1;
        }
    }
    cout << a[n-1] << " " << count << "; ";
    return 0;
}