373. Find K Pairs with Smallest Sums #55
Conversation
docto-rin
left a comment
There was a problem hiding this comment.
お疲れさまです。
lambdaなどを駆使されており、全体的に読みやすく感じました。
いくつかコメントさせていただきました。
| output_count_at_index1 = Array.new(nums1.size, 0) | ||
| output_count_at_index2 = Array.new(nums2.size, 0) | ||
| add_to_heap_if_necessary = lambda do |index1 , index2| | ||
| next unless index1 < nums1.size && index2 < nums2.size | ||
| next unless index2 == output_count_at_index1[index1] && index1 == output_count_at_index2[index2] |
There was a problem hiding this comment.
output_count_at_index1という変数名ですが、変数の更新方法を説明していますが変数自体の意味が不明瞭です。特に2つ目のnext unless条件が何を判断しているか、コードだけだと理解しにくいと感じました。
index1_to_next_index2などはどうでしょうか？もしくは、以下のようにコメントで説明するといいかもしれません。
# 前提: nums1, nums2 は昇順にソートされている
# output_count_at_index1[i] は nums1[i] 行の「列方向の進行度 (次に試す列 j の位置)」を表す
# output_count_at_index2[j] は nums2[j] 列の「行方向の進行度 (次に試す行 i の位置)」を表す| heap.push([nums1[0] + nums2[0], 0, 0]) | ||
| visited = Set.new | ||
| visited << [0, 0] | ||
| add_to_heap_if_necessary = lambda do |index1 , index2| |
There was a problem hiding this comment.
add_to_heap_if_necessaryは説明的ですが少し長いので、コンパクトにpush_if_necessaryなどはどうでしょうか？
There was a problem hiding this comment.
push_if_necessaryいいですね。ありがとうございます。
| heap.push([nums1[0] + nums2[0], 0, 0]) | ||
| visited = Set.new | ||
| visited << [0, 0] | ||
| add_to_heap_if_necessary = lambda do |index1 , index2| |
There was a problem hiding this comment.
些末で恐縮ですが、|index1 , index2|は空白をつめて|index1, index2|でしょうか。
| # step2 他の方の解答を見るj | ||
| - https://github.com/TORUS0818/leetcode/pull/12 | ||
|
|
||
| 候補を二つMinHeapに突っ込んで、最初の組み合わせを取り出してkを満たすまで答えに加える。 | ||
| 取り出した組み合わせを元に次の候補を突っ込む、、、 | ||
| という感じか。 | ||
|
|
||
| > 座標を入れていくと、一番小さいやつが取り出せる魔法の箱を用意する。 | ||
| https://github.com/TORUS0818/leetcode/pull/12/files/aff04af04a728a9d0f33741bb594c698be6aa896..09636a11c0c084c245f82bb029f198c2d0966455#r1697964514 | ||
|
|
||
| こういう箱がある、という発想だと自然な考え方かもしれない。 | ||
|
|
||
| 訪問済みをSetで管理するか配列で管理するかを両方とも試す。 | ||
|
|
||
| LeetCodeで利用可能なRubyのライブラリを確認したところ、push操作がO(1)とあって驚いた。Fibonacci heapというものらしい。 | ||
| https://github.com/intelie/ruby-algorithms/blob/8b2cf66386cd85f05699d055d254215c1e30ba4f/lib/containers/heap.rb#L60-L66 | ||
|
|
There was a problem hiding this comment.
初期化を工夫することで、visited（setや配列）なしでやる方法もあります。
https://discord.com/channels/1084280443945353267/1192736784354918470/1220669329335648346
| while top_k_smallest_pairs.size < k && !heap.empty? | ||
| _, i, j = heap.pop | ||
| top_k_smallest_pairs << [nums1[i], nums2[j]] | ||
| output_count_at_index1[i] += 1 |
There was a problem hiding this comment.
「index1がiのときの次の候補となるindex2」ということが分かる名前になっているとより分かりやすくなるかと思いました。
next_index2_at_index1などでしょうか。
| return [] if nums1.empty? || nums2.empty? || k <= 0 | ||
|
|
||
| top_k_smallest_pairs = [] | ||
| heap = MinHeap.new |
There was a problem hiding this comment.
型を直接そのまま変数名にするより、何が入っているかを書くと読み手の助けになるかと思いました。
| heap.push([nums1[index1] + nums2[index2], index1, index2]) | ||
| end | ||
| while top_k_smallest_pairs.size < k && !heap.empty? | ||
| sum, i, j = heap.pop |
There was a problem hiding this comment.
細かいところですが、上でindex1, index2という変数名を使われているのでこちらもそれに合わせると統一感が取れてよいのではないかと思いました。
| 最初に全ての組み合わせを作って合計の降順にソートして先頭k個を出す方法が浮かんだ。 | ||
| nums1,nums2の個数をM,Nとすると時間計算量はO(M*N*log(M*N))かかるので厳しそう。 |
There was a problem hiding this comment.
これは他の人のコードを見て学んだのですが全探索解も最初にnums1, nums2の長さをkで切ってヒープで最大k個を保持するようにすれば
時間計算量がO(k^2logk), メモリはO(k)になってC++, Javaのような速い言語ならギリギリ間に合うようです。
5ky7/arai60#12 (comment)
pythonやrubyのようなスクリプト言語では流石に厳しいと思いますがご参考まで。
|
|
||
| 訪問済みをSetで管理するか配列で管理するかを両方とも試す。 | ||
|
|
||
| LeetCodeで利用可能なRubyのライブラリを確認したところ、push操作がO(1)とあって驚いた。Fibonacci heapというものらしい。 |
There was a problem hiding this comment.
Fibonacci heap は Dijkstra の高速化で使われるので名前は有名なやつです。中身はほとんどの人が知らないと思います。
|
|
||
| ## Setで管理する方法 | ||
| nums1の長さをM, nums2の長さをNとする。 | ||
| 時間計算量はO(min(M * N * log(M * N), k * log(k)))で、kの最大値は10^4なので1秒以内に間に合う |
There was a problem hiding this comment.
勉強不足で恐縮ですが，「1秒以内に間に合う」という判断に至った過程を教えて欲しいです🙇
There was a problem hiding this comment.
@5ky7
コメントありがとうございます！
Rubyは1オペレーションで平均100 - 1000程度のサイクルを要すると考えると、多めに見積もっても1000 * 10^4 * log(10^4) で大体10^7サイクルくらいかかると考えました。
一般的なクロック周波数3GHzのCPUだと1秒あたり約 3×10⁹ サイクルなので、1秒以内に計算は終わるだろうという見込んでいました。
LeetCodeの出力があまり信用に足らないというのもありますが、実際のところ1.5秒くらいかかっていたので実際はベンチマークを取るのが良いとは思います。
There was a problem hiding this comment.
なるほど，そのようにして計算量から実際の計算時間を見積もるのですね．丁寧に説明していただき，ありがとうございます！
解いた問題
373. Find K Pairs with Smallest Sums
使用言語
Ruby
次に解く問題