LeetCode生活4日目

はじめに

またもやmedium問題らしい。

気長にやっていこう

Top K Frequent Elements

数字の配列numsと整数k(numsの範囲内)がある。それらの数字の中で最も頻出する数字を返せ。

出現回数が同じであればそれらの数字をまとめて配列として返せ。

なおオーダーは O(nlogn)。

問題文これで合ってるかしら。

違った。

この問題は、与えられた整数の配列 nums の中から、出現回数が最も多い k 個の要素を返す問題です。 まず、各要素が何回出現するかカウントします。 その後、頻度の高い順に並べ、最も頻度の高い k 個の要素を選んで返します。

解法1

ということなのでまずは出現回数をカウントしないと。

どうやるか。

あれかな。要素の数字をキーにして、そのvalueは出現回数みたいな感じ。

loopで回してkeyの存在確認をしてあればvalueに+1、なければ新規作成で行こう。あとはkeyをsortしてkこ分取り出せばよき。

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer[]}
def top_k_frequent(nums, k)
    hash = {}
    nums.each do |num|
        hash[num] = (hash[num] || 1) + 1
    end
    hash.sort_by {|key, val| -val}.to_h.keys.slice(0...k)
end

今日の発見。

数字はhashのkeyでシンボルにするとバグる。

keyの存在確認はhash[num]とするだけでいいらしい。

hashのvalueでsortするにはsort_byらしい。

あと忘れてたけど配列の中から切り出すのはsliceをよく使う。

でO番目からO番目とかを表現するにはrangeを使って

最後の数字を含むか否かで rangeの .の数が異なるのは要注意。

含まないのが .3つ。含むのが.2つ。

あと最後のごちゃごちゃしたやつどうにかならんかな。

頭の中でこうなってああなるからこうだよね、ってやったんだけど。

テストはパスしたしいっか。

やった。意外と早い部類かも。かつmediumまたいけた〜

解法2

なんか一番早いやつ見たら今回の問題専用のメソッドがあった

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer[]}
def top_k_frequent(nums, k)
    nums.tally.sort_by {|_, v| v}.last(k).map{|e| e.first}
end

Enumerable#tally (Ruby 3.4 リファレンスマニュアル)

これは知ってたもの勝ちね。

終わりに

2日連続mediumレベルとけた。

なんかhashをよく使うのね。loop回さないでもhash使うと便利ということに最近気づいた。

なんとか解けているから続いている。

完璧主義にならずにゆるく続けていきたい。