کد ++C :
std::pair<int, int> find_equal_sum(const std::vector<int>& arr,const int x)
{
int max = arr[arr.size()-1];//O(1)
//std::vector<int> direct_index_hash(max+1, 0);//O(n)
std::vector<int> direct_index_hash(max+1, 0);//O(k)
for (size_t i = 0; i < arr.size(); i++)//O(n)
direct_index_hash[arr[i]] ++;
for (size_t i = 0; i < arr.size(); i++)//O(n)
{
int diff = x - arr[i];
if (diff <0)
continue;
int diff_count = direct_index_hash[diff];
if (diff == arr[i]){
diff_count--;
}
if (diff_count >0)
return std::make_pair(arr[i], diff);
}
return std::make_pair(-1, -1);//agar 2 onsoor ba majmoo x vojood nadasht
}
اجرای کد
توضیح الگوریتم :
ورودی :
-
arr : آرایه مرتب
-
X : جمع 2 عنصر از آرایه باید این عدد شود.
خروجی :
-
pair(a,b : دو عنصری که جمعشان X هست .
-
متغیر i را 0 می گذاریم
-
تفاضل عدد x با عنصر i ام arr را حساب می کنیم diff=x-arr[i
-
مقدار diff رو درآرایه مرتب arr جست و جو می کنیم اگر موجود بود یعنی [arr[i و diff دو عنصر مورد نظر هستند .
-
i را یک واحد اضافه می کنیم مرحله 2 را تا رسیدن به انتهای آرایه یا جواب تکرار می کنیم.
چون قسمت 2 الگوریتم در بدترین حالت n بار تکرار میشه جست و جو باید در (1)O انجام بشه تا پیچیدگی کلی n بشه پس تنها راهی که وجود داره استفاده از hash table از نوع direct addressing هست (وکتور direct_index_hash داخل کد بالا)
میشه گفت این الگوریتم تقریبا مشابه counting sort هست .
ویرایش:
البته پیچیدگی الگوریتم بالا (O(n+k هست که k طول بزرگترین عدد آرایست (من ساختن وکتور در خط دوم رو (O(n گرفته بودم که درست نیست ).چون سوال حرفی درباره k نزده k خودش میتونه با سرعتی بیشتر از n مثلا n^2 رشد داشته باشه پس نمیشه گفت الگوریتم بالا در بدترین حالت (O(n هست(فقط در صورتی (O(n هست که بازه اعداد حقیقی ورودی تابع محدود باشه)
اگر آرایه sort شده میشه از این روش با (O(n استفاده کرد :
#include <algorithm>
#include <iostream>
#include <vector>
std::pair<int, int> find_equal_sum(const std::vector<int>& arr, const int x)
{
if (arr.size()>1){
int first = 0;
int last = arr.size() - 1;
while (first < last){//O(n)
if (arr[first] + arr[last]>x)
--last;
else if (arr[first] + arr[last]<x)
++first;
else if (arr[first] + arr[last] == x){
return std::make_pair(arr[first], arr[last]);
break;
}
}
}
return std::make_pair(-1, -1);
}
int main()
{
const int x = 19;
std::vector<int> arr{ 5, 7, 8, 11, 12 };
auto res = find_equal_sum(arr, x);
std::cout << res.first << " " << res.second;
return 0;
}