Java da iki Sıralı Dizinin Medyanını Bulmak

Posted by dogukanhan on August 28, 2017 · 1 min read

Medyan : Verilen bir sayı dizisinde terimler büyüklük sırasına göre yazıldıktan sonra ortadaki sayıya medyan denir.
Kaynak: http://www.matematikcanavari.net/2013/04/medyan-nedir.html

Verilen A ve B dizileri sıralanmış olmak üzere medyanını bulma algoritmasının Algoritma Karşılıklılığı O(log(m+n))

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int total = nums1.length+nums2.length;
    if(total%2==0){
        return (findKth(total/2+1, nums1, nums2, 0, 0)+findKth(total/2, nums1, nums2, 0, 0))/2.0;
    }else{
        return findKth(total/2+1, nums1, nums2, 0, 0);
    }
}
 
public int findKth(int k, int[] nums1, int[] nums2, int s1, int s2){
    if(s1>=nums1.length)
        return nums2[s2+k-1];
 
    if(s2>=nums2.length)
        return nums1[s1+k-1];
 
    if(k==1)
        return Math.min(nums1[s1], nums2[s2]);
 
    int m1 = s1+k/2-1;
    int m2 = s2+k/2-1;
 
    int mid1 = m1<nums1.length?nums1[m1]:Integer.MAX_VALUE;    
    int mid2 = m2<nums2.length?nums2[m2]:Integer.MAX_VALUE;
 
    if(mid1<mid2){
        return findKth(k-k/2, nums1, nums2, m1+1, s2);
    }else{
        return findKth(k-k/2, nums1, nums2, s1, m2+1);
    }
}

 

 

Kaynak: https://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/