เราได้รับอาร์เรย์ ให้เรียกว่า arr[] ขององค์ประกอบจำนวนเต็มขนาดใดๆ และจำนวนเต็มบวก k งานคือคำนวณจำนวนคู่ขององค์ประกอบที่ความต่างสัมบูรณ์ไม่เกิน k ที่กำหนด
Arrays เป็นโครงสร้างข้อมูลที่เก็บชุดลำดับขนาดคงที่ขององค์ประกอบชนิดเดียวกัน An array ใช้เก็บชุดข้อมูล แต่บ่อยครั้งมีประโยชน์มากกว่าคิดว่าอาร์เรย์เป็นชุดตัวแปรชนิดเดียวกัน
ตัวอย่าง
อินพุต – int arr[] = {2, 3, 6, 12, 14}, k = 5 เอาต์พุต – count is : 3คำอธิบาย – คู่ที่มีความต่างสัมบูรณ์สูงสุดไม่เกิน k คือ 5 ในตัวอย่างนี้คู่ที่เกิดขึ้นคือ: (2, 3), (2, 6), (3,6) คือ {2, 3, 6} ดังนั้น count คือ 3
อินพุต – int arr[] = {2, 3, 6, 12, 14}, k = 10 เอาต์พุต – count is : 4คำอธิบาย – คู่ที่มีความต่างสัมบูรณ์สูงสุดไม่เกิน k คือ 10 คู่คือ: (2, 3), (2, 6), (3,6), (2, 12), (3, 12), (6, 12) คือ {2, 3, 6, 12} ดังนั้น count คือ 4 เนื่องจากองค์ประกอบสูงสุดคือ 4
อินพุต – int arr[] = {2, 3, 6, 12, 14}, k = 0 เอาต์พุต – count is : 0คำอธิบาย – ไม่มีคู่ที่มีความต่างเป็น 0 ดังนั้น count คือ 0
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- สร้างอาร์เรย์ arr[] และจำนวนเต็มบวก k
- คำนวณความยาวของอาร์เรย์ด้วย length()
- ใช้ตัวแปรชั่วคราวเก็บจำนวนองค์ประกอบ
- ประกาศตัวแปรชั่วคราวสองตัว ให้เป็น first และ last เริ่มต้นที่ 0
- เรียกเมธอด sort เรียงอาร์เรย์ ส่งอาร์เรย์และขนาดอาร์เรย์
- เริ่มลูป for i จาก 0 ถึง i น้อยกว่าขนาดอาร์เรย์
- ในลูป เริ่ม while j < ขนาด AND arr[j] <= arr[i] + k
- ใน while ตรวจสอบ IF count < j-i ตั้งค่า count เป็น j - i และ first เป็น i และ last เป็น j
- คืนค่า count
- พิมพ์ผลลัพธ์
ตัวอย่าง
#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(arr, arr + size);
for (i = 0; i < size; i++) {
while (j < size && arr[j] <= arr[i] + K)
j++;
if (result < (j - i)) {
result = (j - i);
beg = i;
end = j;
}
}
return result;
}
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;
}เอาต์พุต
count is 3
