LeetCode 4日目

4日目の振り返りやっていきます！

今日は同僚と飲む予定なので朝のうちに。

347. Top K Frequent Elements

問題文

整数配列 nums と整数 k が与えられたとき、最も頻度の高い k 個の要素を返せ。答えはどのような順番で返してもよい。

制約条件

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• kは[1, 配列のユニークな要素の数]の範囲にある。
• 答えが一意であることが保証される。

解答

function topKFrequent(nums: number[], k: number): number[] {
    const frequent = new Map<number, number>();

    for (const num of nums) {
        if (frequent.has(num)) {
            frequent.set(num, frequent.get(num) + 1);
        } else {
            frequent.set(num, 1);
        }
    }

    // 出現回数で降順ソート
    const sorted = [...frequent.entries()].sort((a, b) => b[1] - a[1]);

    return [...sorted.keys()].slice(0, k);
}

振り返り

計算量はO(k + n logn) 処理速度もコードの見やすさも問題なさそう。

ただ、TypeScriptのMapを配列にして操作する方法がわからず解くのに１時間半はかかってしまった。

238. Product of Array Except Self

問題文

整数配列 nums が与えられたとき、answer[i] が nums[i] を除く nums のすべての要素の積と等しくなるような配列 answer を返す。

numsの任意の接頭語、接尾語の積は32ビット整数に収まることが保証される。

あなたは、O(n)時間で、除算演算を使わずに実行するアルゴリズムを書かなければならない。

制約条件

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• numsの任意の接頭辞または接尾辞の積は，32ビット整数に収まることが保証される。

解答

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const answer: number[] = Array(n).fill(1);

    let prefix = 1;
    for (let i = 1; i < n; i++) {
        prefix = prefix * nums[i - 1];
        answer[i] = prefix;
    }


    let postfix = 1;
    for (let i = n - 1; i >= 0; i--) {
        answer[i] = answer[i] * postfix;
        postfix = postfix * nums[i];
    }

    return answer
};

振り返り

この問題から１問あたりの時間制限を設けてチャレンジすることにしました。

早速、時間内に解くことができず解説にお世話になりました。。

問題の内容としてはnums[i]のnums[i - 1]までの積（接頭辞の積）とnums[i + 1]以降の（接尾語の積）を乗算するという問題

今思うと制約条件を正しく理解していれば自力で解くことができたのかも。 如何せん英語で問題が書かれており、理解できない場合は翻訳していたりするのだが見落としていることが多々ある。