5月 10, 2024

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 的一些提示是按照著我的思路印出來的(不然真有答案我就不會是這種效能結果了😬),所以我還是會接受並繼續開著他


沒有留言:

張貼留言