主題
題目連結：
題目意譯：
你被給定一個已排序且包含 1 和質數的整數陣列 arr，其中 arr 中的整數彼此相異。你同時也被給定一個整數 k。
對於每一個 i 和 j 值，其中 0 ≦ i < j < arr.length，我們考慮分數 arr[i] / arr[j]。
回傳所有被考慮的分數中第 k 小者。以一個大小為 2 的整數陣列 answer 來回傳你的答案，其中 answer[0] == arr[i] 且 answer[1] arr[j]。
限制：
2 ≦ arr.length ≦ 1000
1 ≦ arr[i] ≦ 3 × 10 ^ 4
arr[0] == 1
對於 i > 0，arr[i] 為一個質數。
arr 中的數字彼此相異並且按照嚴格遞增排序。
1 ≦ k ≦ arr.length × (arr.length - 1) / 2
進階：你可以在比時間複雜度 O(n ^ 2) 好的情況下解出本題嗎？
範例測資：
範例 1：
輸入： arr = [1,2,3,5], k = 3
輸出： [2,5]
解釋： 排序後的分數們為：
1/5 、 1/3 、 2/5 、 1/2 、 3/5 和 2/3。
第三個分數為 2/5。
範例 2：
輸入： arr = [1,7], k = 1
輸出： [1,7]
解題思維：
（令 n = arr.length）
很明顯地，窮舉排序取第 k 小會是 O(n ^ 2 × log(n))。而因為 arr 本來就有排序所以會有辦法可以把後面的排序省下來，進而變成 O(n ^ 2)，但這不符合本題進階的要求。所以在此省略。
如果我們用一個優先佇列（Priority Queue）來儲存分數。一開始可以藉由固定 arr[j]（例如說，統一取 arr[n - 1] 之類的，為了讓現在所有分數盡可能地小），窮舉出所有可能的 arr[i] 並把 (arr[i], arr[j]) 都丟進佇列中。
接著每一次取出最小的分數 (arr[x], arr[y])，如果 arr[y] 還沒有到 arr[i + 1]，則代表 arr[x] 可以與 arr[y - 1] 來配對形成一個較大的分數，所以可以把它丟回進佇列中。重複此步驟 k 次即可找到第 k 小者。
時間複雜度會是 O(n × log(n)) + O(k × log(n)) = O((n + k) × log(n))。
不過我們還有另一種作法，那就是對「答案」進行二分搜尋法（Binary Search）。如這題等。
假設現在猜的分數值是 X（本題可以直接使用浮點數，而不須擔心浮點數誤差。因為根據限制條件，兩個相異分數的最小差異只會是 1 / 30000，而這遠大於一般的浮點數誤差）。接著我們需要檢查小於 X 的分數有多少個，方式如下：
對於每一個 arr[i]，去找到盡可能接近且小於 X 的分數 arr[i] / arr[j]，也就是說要找到一個最小的 j 值使得 arr[i] / arr[j] < X。如果找不到則將 j 視為 n。此時可以看到 arr[i] / arr[j] ～ arr[i] / arr[n - 1] 都是小於 X 的，因此對於單一一個 arr[i] 來說會有 n - j 個分數小於 X。
當然，如果直接這麼做的話這邊的過程就要 O(n ^ 2) 了。不過我們可以看到 arr[i] 與 arr[i + 1] 兩者各自找到的 j 值（設前者為 x 、 後者為 y）會滿足 x ≦ y。會成立的原因是因為 arr 是嚴格遞增排序的。
因此實際上求完 arr[i] 的 j 值後 arr[i + 1] 可以繼承其 j 值繼續「往後」看。因此總體最糟的時間會變成「窮舉所有 i」 + 「j 會從 0 跑到 n」，即 O(n) + O(n) = O(n)。
假設上述過程跑完之後，總計有 c 個小於 X 的分數。如果 c > k，則我們可以把 X 猜小一點；如果 c < k，則可以把 X 猜大一點；如果 c == k，則可以回到上面的過程來找到每個 arr[i] / arr[j] 取最大者即是所求。因為根據定義這些分數是以 arr[i] 作為分子中，數值最大者。而全部總數是 k 個，因此數值最大者才是所求的第 k ?。雌漯N的都太小了）。
而可以看到根據題目的定義，所有分數會介於 0 到 1 之間。因此一開始二分搜的上下界可以分別設為 1 和 0。
而時間複雜度會是 O(n × log(C))，其中 C 是某個常數。而如同上面所述兩個相異分數之間的差異最小只會是 1 / 30000（實際上是 1 / 29989，因為 arr 中只會有 1 和質數存在）。而 1 / 30000 取以 2 為底的對數值略大於 -15，因此二分搜的過程最多只要跑 15 次便可以找到所求的分數。因此本題的時間複雜度也可寫為 O(n × log(15))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
