یافتن دو عنصر در دو آرایه - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۷۴ نفر آنلاین
۰ عضو و ۱۷۴ مهمان در سایت حاضرند

یافتن دو عنصر در دو آرایه

+1 امتیاز
133 بازدید

سلام

دو آرایه n تایی A,B حاوی اعداد حقیقی و یک عدد M داده شده ، می خواهیم دو عدد i,j را در صورت وجود i,j بین 1 تا n پیدا کنیم طوری که :

A[i]+B[j]=M

بهترین الگوریتم برای این مسئله ؟

جواب :nlgn

-----

از ایده ای که اینجا استفاده شده ، عناصر رو بدون مرتب کردن ؛

1- حلقه ای به طول n یک مجموعه universe برای عناصر B بساز

2-اگرتفاضل  قدر مطلق a[i] با M در مجموعه universe بود حتما j در آرایه B هست ؛ پس با یک حلقه به طول O(n) جواب پیدا میشه

وگرنه حلقه ابتدا ++ بشه

در مورد 2 حلقه زمانی اجرا میشه که عنصر مورد نظر hit بشه وگرنه اجرا نمیشه

جوابی که داده فکر کنم از ایده ی binary search استفاده کرده!

سوال شده دی 22, 1393  بوسیله ی Pakniat (امتیاز 382)   2 5 28
ُسلام اشتباه از من بود اون الگوریتم برای اعداد حقیقی (O(n نیست بلکه (O(n+k هست پاسخ قبل رو ویرایش کردم

لطفا وارد شوید یا ثبت نام کنید برای جواب دادن به این سوال.

...