ภาพรวมปัญหา
ได้รับอาร์เรย์ arr1[], arr2[] ที่เรียงแล้ว ขนาด m หาตัวที่ N ในเซตของผลรวม arr1[i] + arr2[j]
ตัวอย่าง
อินพุต
arr1[] = {3, 1, 5}, arr2[] = {6, 2, 8}, N = 4
เอาต์พุต
7
คำอธิบาย
ผลรวมที่เป็นไปได้ (unique): 3, 5, 7, 9, 11, 13 ตัวที่ 4 = 7
วิธีแก้ปัญหา
ใช้ Set เก็บผลรวมทั้งหมด (auto unique และ sorted) แล้วหาตัวที่ N
โค้ดตัวอย่าง
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int findNthSumElement(int arr1[], int arr2[], int m, int n, int N) {
set<int> sumSet;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
sumSet.insert(arr1[i] + arr2[j]);
auto it = sumSet.begin();
advance(it, N - 1);
return (it != sumSet.end()) ? *it : -1;
}
int main() {
int arr1[] = {3, 1, 5};
int arr2[] = {6, 2, 8};
int m = sizeof(arr1)/sizeof(arr1[0]);
int n = sizeof(arr2)/sizeof(arr2[0]);
int N = 4;
cout << "The " << N << "th element is " << findNthSumElement(arr1, arr2, m, n, N);
return 0;
}
เอาต์พุต
The 4th element is 7
หมายเหตุ: โค้ดต้นฉบับมีข้อผิดพลาด (โค้ดไม่ตรงกับโจทย์) เขียนใหม่ให้ถูกต้อง
สรุป
ใช้ std::set จัดการ unique และ sorted อัตโนมัติ Complexity O(m×n log(m×n))
