💬

100日アルゴリズム[11日目・ソート]

2024/04/05に公開

問題

https://leetcode.com/problems/buy-two-chocolates/

回答

function buyChoco(prices: number[], money: number): number {
    const array:number[] = insertSort(prices);

    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {
            const totalCost = array[i] + array[j];
            if (totalCost <= money) {
                return money - totalCost
            }
        }
    }

    return money;
};

function insertSort(prices: number[]):number[] {
    let sortedArray:number[] = prices;
    let n = prices.length;

    for (let i: number = 1; i < n; i++) {
        let current = sortedArray[i];
        let j = i - 1;

        while (j >= 0 && sortedArray[j] > current) {
            sortedArray[j + 1] = sortedArray[j];
            j--;
        }
        sortedArray[j + 1] = current;
    }

    return sortedArray;
}

挿入ソートで対応しました。

Discussion