主題
題目連結：
題目意譯：
給定兩個已排序的索引值從 0 開始數的整數陣列 nums1 和 nums2 以及一整數 k，回傳第 k 小（從 1 開始數）nums1[i] × nums2[i] 之乘積，其中 0 ≦ i < nums1.length 且 0 ≦ j < nums2.length。
限制：
1 ≦ nums1.length, nums2.length ≦ 5 × 10 ^ 4
-10 ^ 5 ≦ nums1[i], nums2[j] ≦ 10 ^ 5
1 ≦ k ≦ nums1.length × nums2.length
nums1 和 nums2 已排序。
範例測資：
範例 1：
輸入： nums1 = [2,5], nums2 = [3,4], k = 2
輸出： 8
解釋： 2 個最小的乘積為：
- nums1[0] × nums2[0] = 2 × 3 = 6
- nums1[0] × nums2[1] = 2 × 4 = 8
第 2 小的乘積為 8。
範例 2：
輸入： nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
輸出： 0
解釋： 6 個最小的乘積為：
- nums1[0] × nums2[1] = (-4) × 4 = -16
- nums1[0] × nums2[0] = (-4) × 2 = -8
- nums1[1] × nums2[1] = (-2) × 4 = -8
- nums1[1] × nums2[0] = (-2) × 2 = -4
- nums1[2] × nums2[0] = 0 × 2 = 0
- nums1[2] × nums2[1] = 0 × 4 = 0
第 6 小的乘積為 0。
範例 3：
輸入： nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
輸出： -6
解釋： 3 個最小的乘積為：
- nums1[0] × nums2[4] = (-2) × 5 = -10
- nums1[0] × nums2[3] = (-2) × 4 = -8
- nums1[4] × nums2[0] = 2 × (-3) = -6
第 3 小的乘積為 -6。
解題思維：
先將 nums1 、 nums2 各自的負數、正數分開存於 n1 、 p1 、 n2 、 p2 之中（儘管我的範例程式碼實際上沒有這樣分拆，但是概念基本一樣），也就是掃過 nums1 、 nums2 並根據正負號去放到相應陣列。
由於 nums1 、 nums2 皆由小排到大，因此 n1 、 p1 、 n2 、 p2 也同樣是由小排到大的。
可以看到我們會有以下四種可能的乘積配對：
n1 的數字配 p2 的數字，其為負數。下稱此種配對為 w；
p1 的數字配 n2 的數字，其為負數。下稱此種配對為 x；
n1 的數字配 n2 的數字，其為正數。下稱此種配對為 y；
p1 的數字配 p2 的數字，其為正數。下稱此種配對為 z。
那要怎麼找到第 k 小的乘積呢？我們可以採取如這題的策略來找——對「答案」進行二分搜尋法（Binary Search），也就是：假設我們已知 [L, R] 區間滿足所有乘積中小於等於 L 之值的數字數量 < k 而所有乘積小於等於 R 之值的數字數量 ≧ k。則我們便可以令一數 M = (L + R) ÷ 2，然後我們去統計有多少乘積小於等於 M，再來判斷我們的新區間要更新成 [L, M] 還是 [M, R]。
一開始我們可以讓 L 為一足夠小的數字（根據題目的數字範圍，-10 ^ 10 便足矣）、R 為一足夠大的數字（同樣根據範圍，10 ^ 10 是足夠的），此時的 [L, R] 即滿足上列性質。問題是，要怎麼檢查有多少乘積之值小於等於 M 呢？
很明顯如果這邊窮舉所有可能的乘積的話，套用二分搜尋法便失去其意義了（因為我們不如直接窮舉然後得到第 k 小，而且還比較簡短）。
首先我們觀察一個例子，以範例三為例：nums1 = [-2,-1,0,1,2] 、 nums2 = [-3,-1,2,4,5] 、 k = 3。此時可以得到
n1 = [-2,-1]、
p1 = [0,1,2]、
n2 = [-3,-1]、
p2 = [2,4,5]。
接著我們分配對種類，也就是分成 w 、 x 、 y 、 z 這四種來討論。如果我們可以得出這四種各自有多少種乘積小於等於 M，則合起來就是「全部」乘積有多少小於等於 M 了。
因此這邊挑全部是正數的 z 來討論（其他種類的情況也會類似以下的討論）：
假設我們現在要檢查的是 M = 4，而現在 p1 = [0,1,2] 、 p2 = [2,4,5]。
現在我們對 p1 中每個數字 p1[i] 去 p2 由右至左找到第一個 p2[j] 使其滿足 p1[i] × p2[j] ≦ M。因為 p2 是由小排到大的，因此我們可以知道當 k = 0 ～ j - 1 時，同樣也會滿足 p1[i] × p2[k] ≦ M。因此 p1[i] 貢獻了 j + 1 個這樣的配對（除非 p2 中所有數字與其乘積皆大於 M，此時貢獻則為 0）。
那麼我們對 p1 中所有數字用藍色這個顏色標記它們於 p2 中第一個滿足上述要求的索引值 j：
p1[0] = 0 得 [2,4,5]、
p1[0] = 1 得 [2,4,5]、
p1[0] = 2 得 [2,4,5]。
從上面可以觀察到藍色標記漸漸地往左，而這並不是巧合。因為 p1 中的數字同樣也是由小排到大，因此當我們由左往右掃時（也就是索引值 i 漸漸增加時），p1[i] 之值要嘛不變、要嘛漸增。因此當 p1[i] 知道 p2[j] 是它的第一個時，p1[i + 1] 便會知道 j + 1 之後（含）的數字不可能會與它的乘積小於等於 M（也就是 p1[i + 1] × p2[k] 必定 > M，對於 M = j + 1 、 j + 2 、……）。
所以我們在由左往右掃 p1 時，我們可以沿用前一次的 j 值來減少搜尋量。
可以看到這個「j」 不會往回跑，因此最多就是把整個 p2 跑完。因此得到 z 這種乘積有多少是小於等於 M 的只需要 O(p1.length + p2.length) 的時間便可以完成。
類似的觀察法可以推至 y 、 x 、 w 種類的配對。因此對於單一一個 M 值，我們可以在
O(p1.length + p2.length)（對於 z 種類的配對） +
O(n1.length + n2.length)（對於 y 種類的配對） +
O(p1.length + n2.length)（對於 x 種類的配對） +
O(n1.length + p2.length)（對於 w 種類的配對）
的時間內完成，也就是
O(nums1.length + nums2.length)
因此我們可以在 O(log(R - L) × (nums1.length + nums2.length)) 內時間找到第 k 小的乘積之值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
