Chúng ta được cung cấp một mảng, giả sử arr [] gồm các phần tử nguyên có kích thước bất kỳ và một số nguyên dương k và nhiệm vụ là tính toán số lượng các cặp phần tử có hiệu số tuyệt đối không vượt quá số nguyên k đã cho.
Mảng là một loại cấu trúc dữ liệu có thể lưu trữ một tập hợp tuần tự có kích thước cố định của các phần tử cùng kiểu. Mảng được sử dụng để lưu trữ một tập hợp dữ liệu, nhưng thường hữu ích hơn nếu coi một mảng là một tập hợp các biến cùng kiểu.
Ví dụ
Input − int arr[] = {2, 3, 6, 12, 14}, k= 5
Output − count is : 3 Giải thích - các cặp có hiệu số tuyệt đối lớn nhất không nhiều hơn k tức là 5 trong ví dụ này, các cặp được hình thành là:(2, 3), (2, 6), (3,6) tức là {2, 3, 6} do đó tính là 3.
Input − int arr[] = {2, 3, 6, 12, 14}, k= 10
Output − count is : 4 Giải thích - các cặp có hiệu số tuyệt đối lớn nhất không nhiều hơn k tức là 10 trong ví dụ này, các cặp được hình thành là:(2, 3), (2, 6), (3,6), (2, 12), (3, 12 ), (6, 12) tức là {2, 3, 6, 12} do đó số lượng là 4 vì các phần tử tối đa là 4.
Input − int arr[] = {2, 3, 6, 12, 14}, k= 0
Output − count is : 0 Giải thích - Vì không có cặp nào có hiệu số là 0 nên số lượng là 0.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Tạo một mảng, giả sử arr [] và một số nguyên dương k
-
Tính độ dài của mảng bằng cách sử dụng hàm length () sẽ trả về giá trị nguyên theo các phần tử trong mảng.
-
Lấy một biến tạm thời sẽ lưu trữ số lượng phần tử.
-
Khai báo hai biến tạm thời cho phép nói, đầu tiên và cuối cùng và khởi tạo bằng 0
-
Gọi phương thức sắp xếp để sắp xếp một mảng và chuyển mảng và kích thước của mảng làm đối số cho hàm.
-
Bắt đầu vòng lặp cho tôi đến 0 và tôi nhỏ hơn kích thước của một mảng
-
Bên trong vòng lặp, bắt đầu trong khi j
-
Bên trong while, kiểm tra IF count
-
Trả lại số lượng
-
In kết quả.
Ví dụ
#include <iostream>
#include <algorithm>
using namespace std;
int countmax(int arr[], int size, int K){
int result = 0;
int i = 0, j = 0;
int beg = 0;
int end = 0;
// Sort the array
sort(arr, arr + size);
// Find max elements
for (i = 0; i < size; i++) {
// Count all elements which are in the range
while (j < size && arr[j] <= arr[i] + K)
j++;
if (result < (j - i)) {
result = (j - i);
beg = i;
end = j;
}
}
// Return the max count
return result;
}
// main function
int main(){
int arr[] = { 2, 3, 6, 12, 14 };
int size = sizeof(arr) / sizeof(arr[0]);
int K = 5;
cout <<"count is "<<countmax(arr, size, K) << endl;
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
Số lượngcount is 3