LeetCode practice: 786. K-th Smallest Prime Fraction

因為每日都有 Daily Question，所以很快就來到第二篇了，前一篇打完後發現打英文太麻煩，就算是用翻譯軟體也不知道對錯，所以還是用中文寫就好😂

Original problem link: 786. K-th Smallest Prime Fraction

這題的題目理解來說很簡單，就是有一組質數陣列，拉出其中任意兩個位置數字相除後的結果，再把所有結果排序後的第幾個位置就是答案。

定義兩個位置 (i, j) 必在 0 ~ 陣列長度中，相除的順序是 i 的值除以 j 的值，從範例來看比較清楚

陣列中每兩個數字計算後的排序由小到大就是 1/5 , 1/3 ... 2/3

因此我初步解題的概念很簡單，反正就是表列所有的結果，再進行排序，最後取得位置的數字即可。這個其實真的是嘗試，因為通常來說這種類型最大魔王是資料的長度，而題目給的長度前提是 

• 2 <= arr.length <= 1000

因此最長就是 1000 ，最終的集合數大約就是 999^2，以量來說有點極限，如果這題是放在 Weekly Contest 總量大概會多100倍，再加上要排序的計算，一定不會 PASS，但很幸運的是目前測試結果還是過了，儘管效能不是很好看（執行時間 17秒、花了 123 MB 的記憶體）

Sample Code

var kthSmallestPrimeFraction = function (arr, k) {
    let sortset = []
    arr.forEach((v, i) => {
        arr.forEach((v2, j) => {
            if (i < j) {
                sortset.push([v, v2]);
            }
        });
    });

    sortset.sort((a, b) => {
        return a[0] / a[1] - b[0] / b[1];
    });
    return sortset[k - 1];
};

實際上 Leetcode 的題目都有提供解決的思考邏輯跟方法，例如這題是

Array, Two Pointers, Binary Search,Sorting, Heap (Priority Queue)

但我只能體會到 Array 跟 Sorting （甚至 Sorting 還只是用內建最簡單的方法），所以能通過只能說運氣好而已。

後記

其實寫這題時我發現一個小狀況，就是我的 VSCode 有加裝 Github 的 Copilot，使用的目的是為了工作時節省一些程式碼的撰寫速度（實際上確實有差）

但測試到 Leetcode 時，當我要試著印出 Test case ，他居然自己把 case 印出來了，這有點讓我警覺之後解題的時候會不會自己就把答案跳出來了😂

但最終我認為工具是工具，寫的人還是要有自己的想法，至少我寫這題的時候 AI 的一些提示是按照著我的思路印出來的（不然真有答案我就不會是這種效能結果了😬），所以我還是會接受並繼續開著他