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

میانه دو آرایه مرتب در سی شارپ (Median of Two Sorted Array)

سعید غریبی

۱۳۹۵.۰۸.۲۰
۰

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

میانه

میانه (به انگلیسی: 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]:int.MaxValue;
            int bValue = bMid<B.Length?B[bMid]:int.MaxValue;

            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]:int.MaxValue;

int bValue = bMid<B.Length?B[bMid]:int.MaxValue;

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);
            Console.WriteLine("median is "+ median);
            Console.ReadKey ();

        }