Median related

Leave a comment

August 20, 2016 by oneOokay

一年以前刷过一次,现在再刷竟然还是花了5+个小时…唉…心酸+心塞….


什么是median? 一个从小到大排列的array:如果array.length为奇数的话, 它的median就是array中的第len/2 + 1个数的值;如果为偶数,它的median就是array中第len/2和第len/2+1这两个数的平均值.

  • median把整个array分成两部分,左边有k个数<=它的值,右边有k个数>=它的值.
  • 一个array里面的第x个数对应的index是x-1.
  • 从index为i的一个数开始(包含它)的第x个数的index是i + x – 1

Find Median from Data Stream/Sliding Window median

Median of Two Sorted Arrays.

求两个sorted array的median,要求O(log(M+N))的时间复杂度.

看到log(M+N)自然的想到了binary search,但是这里如何用binary search,瞬间懵逼.答案是由一个binary search的iterative的解法,但是还没看.

这里其实Divide & Conquer也是可以达到O(log(M+N))的时间复杂度的. 主要是应用一个findKth的想法.

问题转换为:求一个array (A和B merge到一起且sorted)的第k大的数的值. (有k-1个数<=它,k之后的数都>=它)由于array sorted, 第k大的数就是第k个数.

A和B merge的那个array为C. 如果C len为奇数,转换为求C中第len/2+1个数的值;如果C len为偶数,求C中第len/2和第len/2+1个数的平均值.

那么在并不merge A和B的情况下,怎么找C的第k个数?C的第k个数字会是A或者B的某一个index上,要怎么找到这个index?

A和B里面各一个指针:p1和p2. A的第1个数到p1指针之前的数字的个数为x; B的第1个数到p2指针之前的数字的个数为y: 所以当x+y == k – 1时, C的第k个数字就是当前指针p1和p2的较小的那个数.

怎么移动p1和p2?

  1. p1,p2,均从0开始. 要找总的第k大的数字.
  2. 找到A从p1开始的第k/2个数(数的index=p1 + k/2 – 1),值为v1, 和B从p2开始的第k/2个数,值为v2. 比较这两个数的大小.
  3. 如果v1<=v2:说明A中从[p1, p1 +  k/2 -1](一共k/2个数)都会<=B的[p2 + k/2 – 1],所以A[p1 + k/2 – 1]是至多第k-1大的数(因为B[p2 + k/2 – 1]大于等于它). B[p2 + k/2 -1]可能是要求的第k大的数,也可能是第k+n大的数,这里不能确定. 所以A这k/2个数可以安全的扔掉,p1右移k/2(可能overflow,看9和10).反之亦然.
  4. 已经扔掉了k/2个数字,所以下一步还需要扔掉k – k/2个数字. 注意这里不是剩k/2
  5. B的前k/2个数字不确定要扔掉多少个,所以p2指针不变.
  6. 接下来继续对A从p1指针(已经更新了+k/2)开始,B从p2指针开始,找第k-k/2个数字. 所以是一个recursive的解法
  7. 很明显这里就可以出来一个helper method了: findKth(int k, int[] A, int p1, int[]B, int p2).
  8. recursive的解法要考虑何时返回: 显然当k==1的时候要找到第1个大的值,所以返回A[p1]和B[p2]中的较小值.求得了第k大的值.
  9. 但是这里p1和p2并不是一直都是valid的,所以要先于k==1进行判断. (比如一个A为空,那么第一步进来的时候A[0]就是invalid的).
  10. 如果在刚进入findKth method的时候指针的情况:指针可能只在A的len的位置.什么时候会出现这种情况呢? 1) 初始AB一个为空的时候.”[], [1]” 2): recursive时当一个array已经被遍历完的时候. 因为在3和6里面,判断的是p1 + k/2 – 1 < A.length.当p1 + k/2 – 1 == A.length – 1的时候,p1指针右移 k/2.这个时候就overflow了.A已经遍历完了. 所以要先对p1和p2进行判断.当其中一个invalid的时候,直接返回另一个的p + k – 1的值即可.
  11. 接着看A的第k/2大的数的index是[p1 + k/2 – 1]; B的第k/2大的数的index是[p2 + k / 2 – 1]. 这里要对index进行判断,如果A或者B不够了怎么办?
  12. A不够了扔B;B不够了扔A.为什么这样可以呢? 因为假设A只剩1个,B有好多个,一共要扔掉4个,所以A要扔掉2个(不够扔)B要扔掉2个. 如果所求的medium是在A中的话,B就要扔掉4个,所以当前的B这2个一定会被扔掉的;如果所求的medium是在B的话,B这两个也一定会被扔掉,因为A里面只剩1个可以扔,另外的3个都要从B里面扔,所以当前B这2个还是会被扔掉. 所以扔B.
  13. A不够了扔B,怎么扔?可以直接进入下一层recursion findKth(k – k/2, n1, p1, n2, p2 + k/2);或者把val A 附一个Integer.MAX_VALUE,在下一步的判断里面使得val B比它小,从而B被扔掉.
  14. 判断val A和val B的大小,如果val A <= val B,扔A,反之亦然.
  15. 而且从这里可以知道,如果是recursion的话,是可能传入p1==A.length – 1和p2 == B.length – 1的,所以要对10进行判断.
  16. 这里不停的砍掉k/2,最后一定会剩下1. 或者可以分为k/2 和 k- k/2也是一样.因为传入到后来的k一定是>=2的所以k/2和k – k/2都至少为1.
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int k = (m + n) / 2 + 1;
        int v1 = findKth(nums1, 0, nums2, 0, k);
        if ((m + n) % 2 == 1)
            return (double)v1;
        int v2 = findKth(nums1, 0, nums2, 0, k - 1);
        return (v1 + v2)/2.0;
    }
    
    private int findKth(int[] a, int p1, int[] b, int p2, int k){
        if (p1 >= a.length) return b[p2 + k - 1];
        if (p2 >= b.length) return a[p1 + k - 1];
        if (k == 1) return a[p1] > b[p2] ? b[p2] : a[p1];
        
        if (p1 + k / 2 - 1 >= a.length)
            return findKth(a, p1, b, p2 + k / 2, k - k / 2);
        
        if (p2 + k / 2 - 1 >= b.length)
            return findKth(a, p1 + k / 2, b, p2, k - k / 2);
        
        if (a[p1 + k / 2 - 1] > b[p2 + k / 2 - 1])
            return findKth(a, p1, b, p2 + k / 2, k - k / 2);
        
        return findKth(a, p1 + k / 2, b, p2, k - k / 2);
    }

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: