Chúng ta được cung cấp một mảng đã được sắp xếp gồm các phần tử kiểu số nguyên và số giả sử là num và nhiệm vụ là tính số lần phần tử đã cho num xuất hiện trong một mảng .
Đầu vào - int arr [] ={1, 1, 1,2, 3, 4}, num =1
Đầu ra - Đếm số lần xuất hiện (hoặc tần suất) trong một mảng được sắp xếp là - 3
Đầu vào - int arr [] ={2, 3, 4, 5, 5, 6, -7}, num =5
Đầu ra - Đếm số lần xuất hiện (hoặc tần suất) trong một mảng được sắp xếp là - 2
Đầu vào - int arr [] ={-1, 0, 1, 2, 3}, num =7
Đầu ra - Đếm số lần xuất hiện (hoặc tần suất) trong một mảng được sắp xếp là - 0
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Có thể có nhiều cách tiếp cận để giải quyết vấn đề trên.
Cách tiếp cận ngây thơ
-
Khai báo một mảng các phần tử nguyên chứa cả số dương và số âm và một số nguyên của biến số mà chúng ta phải tìm tần suất trong một mảng.
-
Tính kích thước của một mảng và chuyển tất cả dữ liệu vào hàm để xử lý thêm.
-
Khai báo số đếm biến tạm thời để lưu trữ số lần biến num xuất hiện
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng
-
Bên trong vòng lặp, kiểm tra IF num =arr [i] sau đó tăng giá trị của số đếm lên 1
-
Trả lại số lượng
-
In kết quả.
Cách tiếp cận hiệu quả
-
Khai báo một mảng các phần tử nguyên chứa cả số dương và số âm và một số nguyên của biến số mà chúng ta phải tìm tần suất trong một mảng.
-
Tính kích thước của một mảng và chuyển tất cả dữ liệu vào hàm để xử lý thêm.
-
Khai báo số đếm biến tạm thời để lưu trữ số lần biến num xuất hiện
-
Đặt một con trỏ trước tiên là Lower_bound (arr, arr + size, num)
-
Kiểm tra IF đầu tiên =(arr + size) || (* đầu tiên! =num) sau đó trả về 0
-
Đặt con trỏ cuối là upper_bound (đầu tiên, arr + size, num)
-
Đặt số lượng là cuối cùng - đầu tiên
-
Số lần trả lại
-
In kết quả
Ví dụ (cách tiếp cận ngây thơ)
#include <iostream>
using namespace std;
int frequency_count(int arr[], int num, int size){
int count = 0;
for(int i=0; i<size; i++){
if(num==arr[i]){
count++;
}
}
return count;
}
int main(){
int arr[] = {1, 1, 1,2, 3, 4};
int num = 1;
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of occurrences (or frequency) in a sorted array are: "<<frequency_count(arr, num, size);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of occurrences (or frequency) in a sorted array are: 3
Ví dụ (Phương pháp Tiếp cận Hiệu quả)
# include <bits/stdc++.h>
using namespace std;
int frequency_count(int arr[], int num, int size){
int *first = lower_bound(arr, arr+size, num);
if (first == (arr + size) || *first != num){
cout<<"The Element is not present in an array ";
return 0;
}
int count = 0;
int *last = upper_bound(first, arr+size, num);
count = last - first;
return count;
}
int main(){
int arr[] = {1, 1, 1, 2, 3, 4};
int num = 1;
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of occurrences (or frequency) in a sorted array are: "<<frequency_count(arr, num, size);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of occurrences (or frequency) in a sorted array are: 3