เราได้รับอาร์เรย์ สมมติว่า arr[] ขององค์ประกอบจำนวนเต็มของขนาดที่กำหนดและจำนวนเต็มบวก k และภารกิจคือการคำนวณจำนวนคู่ขององค์ประกอบเหล่านั้นซึ่งความแตกต่างแน่นอนไม่เกินจำนวนเต็มที่กำหนด k
อาร์เรย์ประเภทโครงสร้างข้อมูลที่สามารถจัดเก็บคอลเล็กชันแบบต่อเนื่องที่มีขนาดคงที่ขององค์ประกอบประเภทเดียวกัน อาร์เรย์ใช้เพื่อจัดเก็บชุดข้อมูล แต่มักจะมีประโยชน์มากกว่าที่จะคิดว่าอาร์เรย์เป็นชุดของตัวแปรประเภทเดียวกัน
ตัวอย่าง
Input − int arr[] = {2, 3, 6, 12, 14}, k= 5
Output − count is : 3 คำอธิบาย − คู่ที่มีความแตกต่างสัมบูรณ์สูงสุดไม่เกิน k เช่น 5 ในตัวอย่างนี้ คู่ที่เกิดขึ้นคือ (2, 3), (2, 6), (3,6) เช่น {2, 3, 6} ดังนั้นการนับ คือ 3.
Input − int arr[] = {2, 3, 6, 12, 14}, k= 10
Output − count is : 4 คำอธิบาย − คู่ที่มีความแตกต่างสัมบูรณ์สูงสุดไม่เกิน k เช่น 10 ในตัวอย่างนี้ คู่ที่เกิดขึ้นคือ (2, 3), (2, 6), (3,6), (2, 12), (3, 12 ), (6, 12) เช่น {2, 3, 6, 12} ดังนั้นการนับคือ 4 เนื่องจากองค์ประกอบสูงสุดคือ 4
Input − int arr[] = {2, 3, 6, 12, 14}, k= 0
Output − count is : 0 คำอธิบาย − เนื่องจากไม่มีคู่ที่ต่างกันเท่ากับ 0 ดังนั้นการนับจึงเป็น 0
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
สร้างอาร์เรย์ สมมติว่า arr[] และจำนวนเต็มบวก k
-
คำนวณความยาวของอาร์เรย์โดยใช้ฟังก์ชัน length() ที่จะคืนค่าจำนวนเต็มตามองค์ประกอบในอาร์เรย์
-
ใช้ตัวแปรชั่วคราวที่จะเก็บจำนวนองค์ประกอบ
-
ประกาศตัวแปรชั่วคราว 2 ตัว คือ ตัวแรกและตัวสุดท้าย และกำหนดค่าเริ่มต้นด้วย 0
-
เรียกวิธีการจัดเรียงเพื่อจัดเรียงอาร์เรย์และส่งผ่านอาร์เรย์และขนาดของอาร์เรย์เป็นอาร์กิวเมนต์ของฟังก์ชัน
-
เริ่มวนรอบสำหรับ i ถึง 0 และฉันน้อยกว่าขนาดของอาร์เรย์
-
ภายในลูป เริ่มด้วย j
-
ข้างในในขณะที่ตรวจสอบ IF 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 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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
count is 3
