میانه دو آرایه مرتب در جاوا (median of two sorted arrays)

در این جلسه تیم کدگیت را با آموزش میانه دو آرایه مرتب در جاوا همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:

  1. آشنایی با آرایه
  2. آشنایی با متد
  3. آشنایی با روش بازگشتی
  4. آشنایی با if

میانه

میانه (به انگلیسی: Median) در آمار و نظریه احتمالات نوعی سنجش گرایش به مرکز است. میانه عددی است که یک جمعیت آماری و یا یک توزیع احتمالی را به دو قسمت مساوی تقسیم می‌کند. اگر تعداد جمعیت آماری زوج باشد، میانه با میانگین دو عضو جمعیت که در وسط جمعیت آماری قرار دارند، محاسبه می‌شود(ویکیپدیا).

میانه دو آرایه مرتب در جاوا

برای محاسبه میانه دو آرایه مرتب در جاوا ما از روش بازگشتی استفاده کردیم. ایده کار ما بدین صورت است که ما دو آرایه داریم که مرتب هستند و به راحتی میتوان میانه این دو را پیدا کرد.حال ما اگر میانه ها را با هم مقایسه کنیم حالات زیر رخ میدهد:

  1. میانه ها دو آرایه برابر باشند در این صورت پاسخ دقیقا همین است.
  2. میانه آرایه اول کوچکتر از آرایه دوم باشد در این صورت از خانه اول تا خانه ماقبل آرایه اول را حذف میکنیم و برعکس همین کار را بر روی آرایه دوم انجام میدهیم.
  3. میانه آرایه اول بزرگتر از آرایه دوم باشد. در این صورت برعکس حالت 2 را انجام میدهیم.

موارد بالا را آنقدر انجام میدهیم تا به حالت اول برسیم یا تعداد خانه های آرایه برابر 1 شود.کد میانه دو آرایه مرتب در جاوا به صورت زیر است:

در کد میانه دو آرایه مرتب در جاوا شامل دو متد است:

  1. Findmediansortedarray: این متد میانه دو آرایه را بر میگرداند.
  2. Findkth: این متد یکی از میانه های دو آرایه (ممکن است آرایه دو میانه داشته باشد) را بر اساس ورودی بر میگرداند(وقتی تعداد خانه های دو آرایه زوج باشد تعداد میانه ها 2 است و میانه اصلی میانگین این دو عدد است)

در متد Findmediansortedarray ابتدا طول هر دو آرایه را میگیرد و سپس بر اساس زوج یا فرد بودن تعداد خانه های 2 آرایه، میانه را به کمک متد findkth بدست می آورد. متد findkth به عنوان ورودی دو آرایه(A و B) و نقطه شروع هر آرایه(مثلا astart) و تعداد خانه هایی که باید بررسی کند(k) را میگیرد.سپس با توجه به حالات توضیح داده شده یک میانه را برمیگرداند.

تست میانه دو آرایه مرتب در جاوا

برای تست کدهای بالا،کد main زیر را بزنید:

پسورد: www.codegate.ir

 

دسته : java, جاوا, حل مسائل با جاوا, ساختمان داده در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz