4 Median of Two Sorted Arrays

Concept

Part 1 - 不斷比較nums1跟nums2的中位數，砍掉一半的元素

• 這題基本的概念是想要不斷砍掉一半的元素，讓搜尋變得很有效率。
• 問題是，要怎麼怎麼知道哪一些元素是我們可以忽略的?
• 基本想法是，只要不可能是我們最後想求的中位數，就可以忽略。
• 下一個問題是，要怎麼知道哪些元素不可能是我們想求的中位數?

• 先隨意觀察兩個矩陣，我們知道ans是4。

   nums1 = [1, 2, 5, 7]
   nums2 = [3, 4, 8]
  

• 不過知道答案是4的目的不是要讓我們想到可以解出答案的演算法，現在只是要先確保我們砍掉一半的元素不會誤砍到4。

• 因為已經參考了答案，知道要取兩個矩陣的中位數。
• nums1的中位數是$$(2+5)/2=3.5$$，意義是可以將nums1分成兩半，一半比3.5大，一半比3.5小。
• nums2的中位數是4，用途也是將nums2切成兩半。
• 在這個例子中，nums1的中位數 < nums2的中位數。
• 我們想求的ans可以將nums1跟nums2切成兩半，意義是，總共有一半的元素比ans小、一半比ans大。
• 所以ans不可能落在nums1的左半邊，不然就會有超過一半的元素比ans大；同理，也不可能落在nums2的右半邊，不然就會有超過一半的元素比ans小。

Part 2 - 確保可以求得答案的演算法

• 雖然有了上面的concept，但還沒有可以求得答案的感覺。
• 從最上層的來看，我們不知道nums1+nums2的元素有奇數還是偶數個。所以寫一個general的方法直接考慮兩種case。
• 如果共有奇數個，l==r；如果共有偶數個，l==r-1。只要getkth(A, 0, B, 0, l)跟getkth(A, 0, B, 0, r)都能傳回對的答案，那答案就會對。

  public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int l = (m + n + 1) / 2;
        int r = (m + n + 2) / 2;
        return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
    }
  

• 有一個疑問是，getkth()的參數為什麼是這樣?

  double getkth(int[] A, int aStart, int[] B, int bStart, int k)
  

• 首先要了解，getkth()的目的是什麼?
• getkth()的目的就是要取到A跟B矩陣中第k大的元素。
• 所以最上層是呼叫getkth(A, 0, B, 0, l)跟getkth(A, 0, B, 0, r)，取得第l大跟第r大的元素。
• 因為我們需要取到A跟B裡面第k大的element，所以把A跟B傳進去是必要的。
• 接下來的再一次呼叫，因為已經排除掉

============= 待整理

• 因為現在是要找第k大的element，而且其實我們傳進來的k的大小會是中位數的那一格(例如總共有7個element，那k就會是4)。所以中位數的取法就是aMid = A[aStart + k/2 - 1];，然後aStart + k/2 - 1 < A.length只是要檢查大小不要超過array長度。

   if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1];
  

• 這邊是終止條件，首先如果aStart超過A的長度，表示現在只是在求B[bStart]這個index開始第k大的element。如果是k==1，表示已經砍到剩下要求目前最小的那個element了，而且分別是從A[aStart]跟B[bStart]開始求，所以自然就是取min(A[aStart], B[bStart])了。

if (aStart > A.length - 1) return B[bStart + k - 1];            
    if (bStart > B.length - 1) return A[aStart + k - 1];                
    if (k == 1) return Math.min(A[aStart], B[bStart]);