用LeetCode寫日記-Day24

靠….我現在才發現我LeetCode拼錯了…少打一個t…
花了點時間把所有錯字訂正…

Day24: Sort By

問題描述：

Given an array arr and a function fn, return a sorted array sortedArr. You can assume fn only returns numbers and those numbers determine the sort order of sortedArr. sortedArray must be sorted in ascending order by fn output.

You may assume that fn will never duplicate numbers for a given array.

問題難度：Easy

問題限制：

• arr is a valid JSON array
• fn is a function that returns a number
• 1 <= arr.length <= 5 * 105

我的解題過程：

題目要我們做出一個可以升序排列的function。

看完題目第一個想法是這次來使用reduce()吧，雖然用sort()很容易就做得出來，但之前印象有用過了，這次來挑戰一下用其他方式。

首先，我們先創建一個sortArr的變數：

const sortArr = arr.reduce(() => {}, [])

reduce的語法：reduce(callbackFn, initialValue)

之所以在initialValue 這個參數使用空陣列，是因為這個初始的空陣列是用來累計已排序的結果，而在排序的過程中會不斷更新。

接下來處理callback function：

我們的function 會傳入兩個參數：accumulator跟currentValue，並且我們創建一個新的變數currentFnValue ****裡面放的是經過fn處理過後的值：

const sortedArr = arr.reduce((acc, current) => {
	const currentFnValue = fn(current)
}

之後我們需要一個變數來存放布林值，這個變數是用來標記當前元素是否已經被插入到正確的位置。

let inserted = false;

接下來就要處理兩個數之間的比較，我們在創建一個變數accFnValue ，這個變數存放對已排序的元素使用函數 fn 取得比較值：

for (let i = 0; i < acc.length; i++) {
        const accFnValue = fn(acc[i]);
        if (currentFnValue < accFnValue) {
            acc.splice(i, 0, current);
            inserted = true;
            break;
        }
    }

後面的判斷式是：如果當前元素的比較值小於已排序元素的比較值，表示找到了插入的位置。

然後使用splice()把該元素放到現在i的位置。

最後再加上**if (!inserted) { acc.push(current); } ，**這是當我們現在這個數字比我們要比較的數字都還要大時，就把它插入在array的最後一個位子。

這樣我們整個function借完成了。

結果最後提交出現了問題….Testcases passed, but took too long.

超時了…..

我的code:

var sortBy = function(arr, fn) {
    const sortArr = arr.reduce((acc, current) => {
        const currentFnValue = fn(current);
        let inserted = false;
        for (let i = 0; i < acc.length; i++) {
            const accFnValue = fn(acc[i]);
            if (currentFnValue < accFnValue) {
                acc.splice(i, 0, current);
                inserted = true;
                break;
            }
        }
        if (!inserted) {
            acc.push(current);
        }

        return acc;
    }, []);

    return sortArr;
    
};

其他解法：

var sortBy = function(arr, fn) {
    return arr.sort((a, b) => fn(a) - fn(b));
};

結論：

我幹嘛沒事找事做…10分鐘內可以解決的問題要搞到花了快1個小時…重點是還不能提交…
搞了老半天還是用sort()的方式…
唯一的好處是又複習了一次reduce()