เราได้รับอาร์เรย์ที่เรียงแล้วขององค์ประกอบจำนวนเต็มและตัวแปรจำนวนเต็ม x และงานคือการสร้างคู่จากอาร์เรย์ที่กำหนดและคำนวณผลรวมขององค์ประกอบในคู่และตรวจสอบว่าผลรวมที่คำนวณได้น้อยกว่า x หรือไม่
อินพุต − int arr[] = {2, 7, 1, 0, 8}, int x = 8
เอาต์พุต − นับคู่ในอาร์เรย์ที่เรียงแล้วที่ผลรวมน้อยกว่า x คือ − 4
คำอธิบาย − คู่ที่สามารถสร้างได้จากอาร์เรย์ที่กำหนดคือ: (2, 7) = 9(มากกว่า x), (2, 1) = 3(น้อยกว่า x), (2, 0) = 2(น้อยกว่า x), (2, 8) = 10(มากกว่า x), (7, 1) = 8(เท่ากับ x), (7, 0) = 7(น้อยกว่า x), (7, 8) = 15(มากกว่า x), (1, 0) = 1(น้อยกว่า x), (1, 8) = 8(เท่ากับ x), (0, 8) = 8(เท่ากับ x) ดังนั้นคู่ที่มีผลรวมน้อยกว่า x คือ (4, 0) และ (2, 2) จำนวนคู่ที่ผลรวมน้อยกว่า x คือ 4
อินพุต − int arr[] = {2, 4, 6, 8}, int x = 10
เอาต์พุต − นับคู่ในอาร์เรย์ที่เรียงแล้วที่ผลรวมน้อยกว่า x คือ − 2
คำอธิบาย − คู่ที่สามารถสร้างได้จากอาร์เรย์ที่กำหนดคือ: (2, 4) = 6(น้อยกว่า x), (2, 6) = 8(น้อยกว่า x), (2, 8) = 10(เท่ากับ x), (4, 6) = 10(เท่ากับ x), (4, 8) = 12(มากกว่า x), (6, 8) = 14(มากกว่า x) ดังนั้นจำนวนคู่ที่ผลรวมน้อยกว่า x คือ 2
วิธีการที่ใช้ในโปรแกรมด้านล่าง
สามารถมีหลายวิธีในการแก้ปัญหาที่กำหนด คือ วิธีเรียบง่ายและวิธีที่มีประสิทธิภาพ มาดู วิธีเรียบง่าย ก่อน
รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชัน
ประกาศตัวแปรชั่วคราว count เพื่อเก็บจำนวนคู่ที่ผลรวมน้อยกว่า x
เริ่มลูป FOR จาก i = 0 ถึงขนาดของอาร์เรย์
ภายในลูป เริ่มลูป FOR อีกอันจาก j = i + 1 ถึงขนาดของอาร์เรย์
ภายในลูป คำนวณผลรวมเป็น arr[i] + arr[j] และตรวจสอบ IF sum < x แล้วเพิ่ม count ขึ้น 1
คืนค่า count
พิมพ์ผลลัพธ์
วิธีที่มีประสิทธิภาพ
รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชัน
ประกาศตัวแปรชั่วคราว count เพื่อเก็บจำนวนคู่ที่ผลรวมน้อยกว่า x
ตั้ง arr_0 เป็น 0 และ arr_1 เป็น size-1
เริ่มลูป FOR จาก arr_0 ถึง arr_1
ภายในลูป ตรวจสอบ IF arr[arr_0] + arr[arr_1] < x แล้วตั้ง count เป็น count + (arr_1 - arr_0) และเพิ่ม arr_0++ มิฉะนั้นลด arr_1 ลง 1
คืนค่า count
พิมพ์ผลลัพธ์
ตัวอย่าง (วิธีเรียบง่าย)
#include <iostream> using namespace std; int pair_sum(int arr[], int size, int x){ int count = 0; int sum = 0; for(int i = 0 ;i <size ; i++){ for(int j = i+1; j<size; j++){ sum = arr[i] + arr[j]; if(sum < x){ count++; } } } return count; } int main(){ int arr[] = {2, 7, 1, 0, 8}; int size = sizeof(arr) / sizeof(arr[0]); int x = 8; cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x); return 0; }เอาต์พุต
ถ้าเรารันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −
Count of pairs in a sorted array whose sum is less than x are: 4
ตัวอย่าง (วิธีที่มีประสิทธิภาพ)
#include <iostream> using namespace std; int pair_sum(int arr[], int size, int x){ int arr_0 = 0; int arr_1 = size-1; int count = 0; while(arr_0 < arr_1){ if (arr[arr_0] + arr[arr_1] < x){ count = count + (arr_1 - arr_0); arr_0++; } else{ arr_1--; } } return count; } int main(){ int arr[] = {2, 7, 1, 0, 8}; int size = sizeof(arr) / sizeof(arr[0]); int x = 8; cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x); return 0; }เอาต์พุต
ถ้าเรารันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −
Count of pairs in a sorted array whose sum is less than x are: 4
