Chúng ta được cho với một mảng các phần tử khác nhau, từ giá trị 1 đến n. Một số yếu tố được lặp lại và một số bị thiếu. Mục đích là tìm tần số của tất cả các phần tử trong O (n) thời gian và O (1) không gian phụ.
Đầ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ử cao nhất là 5, kết quả hiển thị 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ử cao nhất là 5, kết quả hiển thị số lần mỗi phần tử xuất hiện trong mảng.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chương trình dưới đây hoạt động cho các mảng có số từ 1 đến 10.
-
Hàm printfrequency (int arr [], int n) nhận một mảng và kích thước n của nó làm đầu vào và trả về số lượng các số từ 1 đến 10 có trong mảng.
-
Chúng tôi tạo arr [i] =arr [i] -1 để mỗi chỉ mục lưu trữ tần suất của số i, 1 chỉ mục được lưu trữ 0, v.v.
-
Sử dụng vòng lặp for ở mỗi tần số arr [arr [i]% 10] thêm 10 vào giá trị ban đầu.
-
Đối với x lần 10 sẽ được thêm vào nếu số i xuất hiện x lần trong mảng.
-
Hiện đang sử dụng tần số in vòng lặp for bằng cách sử dụng arr [i] / 10 cho tất cả các phần tử i + 1 tại chỉ mục i.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
void printfrequency(int arr[],int n){
int i=0;
//1 becomes 0, 2 becomes 1 .....10 becomes 9 so arr[i] will have count of i
for ( i =0; i<n; i++)
arr[i] = arr[i]-1;
//as numbers are between 1-10 add 10 to all (num%10 is num itself)
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;
} Đầu ra
1 -> 0 2 -> 2 3 -> 2 4 -> 0 5 -> 1 6 -> 1 7 -> 3 8 -> 2 9 -> 5 10 -> 0