تیم برنامه نویسی کدگیت

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

سعید غریبی

۱۳۹۵.۰۷.۲۳
۰

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

میانه

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

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

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

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

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

 public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
         int m=nums1.length;
         int n=nums2.length;
         if((m+n)%2==0){
             return (
                 findKth((m+n)/2,    nums1, 0,  nums2, 0) +
                 findKth((m+n)/2+1,  nums1, 0, nums2, 0)
             )/2.0;
         }else{
             return findKth((m+n)/2+1, nums1, 0, nums2, 0);
         }
     }

     public static int findKth(int k, int [] A, int aStart, int[] B, int bStart){
         if(aStart>=A.length){
             return B[bStart+k-1];
         }
         if(bStart>=B.length){
             return A[aStart+k-1];
         }
         if(k==1)
             return Math.min(A[aStart], B[bStart]);

         int aMid = aStart+k/2-1;
         int bMid = bStart+k/2-1;

         int aValue = aMid<A.length?A[aMid]:Integer.MAX_VALUE;
         int bValue = bMid<B.length?B[bMid]:Integer.MAX_VALUE;

         if(aValue<bValue){
             return findKth(k-k/2, A, aMid+1, B, bStart);
         }else{
             return findKth(k-k/2, A, aStart, B, bMid+1);
         }

     }

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

int m=nums1.length;

int n=nums2.length;

if((m+n)%2==0){

return (

findKth((m+n)/2, nums1, 0, nums2, 0) +

findKth((m+n)/2+1, nums1, 0, nums2, 0)

)/2.0;

}else{

return findKth((m+n)/2+1, nums1, 0, nums2, 0);

}

public static int findKth(int k, int [] A, int aStart, int[] B, int bStart){

if(aStart>=A.length){

return B[bStart+k-1];

}

if(bStart>=B.length){

return A[aStart+k-1];

}

if(k==1)

return Math.min(A[aStart], B[bStart]);

int aMid = aStart+k/2-1;

int bMid = bStart+k/2-1;

int aValue = aMid<A.length?A[aMid]:Integer.MAX_VALUE;

int bValue = bMid<B.length?B[bMid]:Integer.MAX_VALUE;

if(aValue<bValue){

return findKth(k-k/2, A, aMid+1, B, bStart);

}else{

return findKth(k-k/2, A, aStart, B, bMid+1);

}

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

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

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

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

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

  public static void main(String[] args) {
         int nums1[] = {1, 12, 15, 26, 38};
         int nums2[] = {2, 13, 17, 30, 45};

         double median = findMedianSortedArrays(nums1, nums2);
         System.out.println("median is "+ median);

     }