akmhmgc · akmhmgc · Oct 11, 2025 · nanae772 · Oct 12, 2025 · oda
diff --git a/703/step1.md b/703/step1.md
@@ -0,0 +1,45 @@
+# step1 何も見ずに解く
+
+Nをスコアの長さとする。Mをadd操作の回数とする。
+最初のスコアをソートしておくと、k番目のスコアはO(1)で取り出せる。
+新しいスコアを追加する時は二分探索を使うとO(logN)で入れる場所を探せる。
+ただ、配列の途中に挿入するときにO(N + M)の計算量がかかるので、最終的な時間計算量は
+M * (log(M + N) + (M + N))となり、O(M * (M + N))となり、M,Nの最大値が10^4なので間に合わない気がする。
+
+```ruby
+class KthLargest
+
+=begin
+    :type k: Integer
+    :type nums: Integer[]
+=end
+    def initialize(k, nums)
+        raise ArgumentError, "k must be positive integer" if k <= 0
+        @k = k
+        @sorted_nums = nums.sort.reverse
+    end
+
+
+=begin
+    :type val: Integer
+    :rtype: Integer
+=end
+    def add(val)
+        return @sorted_nums[@k - 1] if @sorted_nums.size >= @k && @sorted_nums[@k - 1] >= val
+
+        index = @sorted_nums.bsearch_index { |num| num <= val }
+        if index.nil?
+            @sorted_nums << val
+        else
+            @sorted_nums.insert(index, val)
+        end
+        @sorted_nums[@k - 1]
+    end
+end
+```
+
+なぜか間に合った。テストケースに厳しいものが少なかったのかも。
+一応Rubyのinsertメソッドの実装を見たが、やはりO(N)かかるっぽい。まあそりゃそうか。
+
+今のコードでは、scoreは降順に並んでいて、@sorted_nums[@k - 1]より小さい値、つまり配列の後にくる値の挿入をスキップしている。
+配列の挿入は後ろであればあるほどコストが小さいはずなので昇順にして、前の方に挿入する時にスキップした方がマシだったかもしれない。
diff --git a/703/step2.md b/703/step2.md
@@ -0,0 +1,130 @@
+# step2 他の方の解答を見る
+
+- https://github.com/Ryotaro25/leetcode_first60/pull/9
+
+MinHeapで実装する。
+小さい順に上位k個数の値を保持しておけば良い。
+Heapに値を追加する時の時間計算量はO(logN)
+一番上の値を取り出した後にHeapの順を直す時の時間計算量もO(logN)
+なのでnumsの長さをN, addが呼ばれる回数をMとすると、
+最初にnumを入れるのにO(N*logN)でaddのクエリは合計で(M * log(k))になる。
+なのでO(NlogN)
+空間計算量はO(M + N)
-なのでnumsの長さをN, addが呼ばれる回数をMとすると、
-最初にnumを入れるのにO(N*logN)でaddのクエリは合計で(M * log(k))になる。
-なのでO(NlogN)
-空間計算量はO(M + N)
+なのでnumsの長さをN, addが呼ばれる回数をMとすると、
+addは1回O(log k)なので、初期化O(N logk)、クエリの処理O(M logk)。
+よって時間計算量はO(N logk + M logk)=O((N+M)logk)。
+空間計算量はO(k)。
-なのでnumsの長さをN, addが呼ばれる回数をMとすると、
-最初にnumを入れるのにO(N*logN)でaddのクエリは合計で(M * log(k))になる。
-なのでO(NlogN)
-空間計算量はO(M + N)
+なのでnumsの長さをN, addが呼ばれる回数をMとすると、
+addは1回O(log k)なので、初期化O(N logk)、クエリの処理O(M logk)。
+よって時間計算量はO(N logk + M logk)=O((N+M)logk)。
+空間計算量はO(k)。
+
+```ruby
+class MinHeap
+    def initialize
+        @heap = []
+    end
+
+    def peek
+        @heap.first
+    end
+
+    def push(val)
+        @heap << val
+        sift_up(@heap.size - 1)
+    end
+
+    def pop
+        return nil if @heap.empty?
+
+        swap(0, @heap.size - 1)
+        min = @heap.pop
+        sift_down(0)
+        min
+    end
+
+    def size
+        @heap.size
+    end
+
+    private
+
+    def parent_index(index)
+        (index - 1) / 2
+    end
+
+    def left_child_index(index)
+        2 * index + 1
+    end
+
+    def right_child_index(index)
+        2 * index + 2
+    end
+
+    def sift_up(child)
+        parent = parent_index(child)
+        return if parent < 0 || @heap[parent] <= @heap[child]
+
+        swap(child, parent)
+        sift_up(parent)
+    end
+
+    def sift_down(parent)
+        left = left_child_index(parent)
+        right = right_child_index(parent)
+        smallest = parent
+        smallest = left if left < @heap.size && @heap[smallest] > @heap[left]
+        smallest = right if right < @heap.size && @heap[smallest] > @heap[right]
+        return if smallest == parent
+
+        swap(parent, smallest)
+        sift_down(smallest)
+    end
+
+    def swap(index1, index2)
+        @heap[index1], @heap[index2] = @heap[index2], @heap[index1]
+    end
+end
+
+
+
+class KthLargest
+
+=begin
+    :type k: Integer
+    :type nums: Integer[]
+=end
+    def initialize(k, nums)
+        raise ArgumentError, "k must be positive integer" if k <= 0
+        raise ArgumentError, "Initial array size is too small to determine the top #{k}" if k > nums.size + 1
-        raise ArgumentError, "k must be positive integer" if k <= 0
-        raise ArgumentError, "Initial array size is too small to determine the top #{k}" if k > nums.size + 1
+        raise ArgumentError, "k '#{k}' must be positive integer" if k <= 0
+        raise ArgumentError, "Initial array size '#{nums.size}' is too small to determine the top k '#{k}'" if k > nums.size
-        raise ArgumentError, "k must be positive integer" if k <= 0
-        raise ArgumentError, "Initial array size is too small to determine the top #{k}" if k > nums.size + 1
+        raise ArgumentError, "k '#{k}' must be positive integer" if k <= 0
+        raise ArgumentError, "Initial array size '#{nums.size}' is too small to determine the top k '#{k}'" if k > nums.size
+        @k = k
+        @top_k = MinHeap.new
+        nums.each { |num| add(num) }
+    end
+
+
+=begin
+    :type val: Integer
+    :rtype: Integer
+=end
+    def add(val)
+        if @top_k.size < @k
+            @top_k.push(val)
+        elsif @top_k.peek < val
+            @top_k.pop
+            @top_k.push(val)
+        end
+        @top_k.peek
+    end
+end
+```
+
+https://github.com/shintaroyoshida20/leetcode/pull/13/files/db18f87a811ced86f26a72e4ee842f1b99d71b15#r2052161956
+
+LeetCode環境でRubyは`Module: Algorithms`が使えるらしい。初めて知った。
+https://www.rubydoc.info/github/kanwei/algorithms/Algorithms
+
+
+https://github.com/fhiyo/leetcode/pull/10/files/0ee4b594d9657627d07ef9810b8f695611e366ac#r1605950261
+
+メソッド単位でmutexを取る前提だと、topで値を返さないと
+- スレッドA
+  - 1. top
+  - 3. pop
+スレッドB
+  - 2. pop
+
+上の順番で処理が走ると不整合が起きる。
+
diff --git a/703/step3.md b/703/step3.md
@@ -0,0 +1,99 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+class MinHeap
+    def initialize
+        @heap = []
+    end
+
+    def size
+        @heap.size
+    end
+
+    def push(val)
+        @heap << val
+        sift_up(@heap.size - 1)
+    end
+
+    def pop
+        swap(0, @heap.size - 1)
+        min_val = @heap.pop
+        sift_down(0)
+        min_val
+    end
+
+    def peek
+        @heap.first
+    end
+
+    private
+
+    def parent_index(index)
+        (index - 1) / 2
+    end
+
+    def left_child_index(index)
+        index * 2 + 1
+    end
+
+    def right_child_index(index)
+        index * 2 + 2
+    end
+
+    def swap(index1, index2)
+        @heap[index1], @heap[index2] = @heap[index2], @heap[index1]
+    end
+
+    def sift_up(child)
+        parent = parent_index(child)
+        return if parent < 0 || @heap[parent] <= @heap[child]
+
+        swap(child, parent)
+        sift_up(parent)
+    end
+
+    def sift_down(parent)
+        left = left_child_index(parent)
+        right = right_child_index(parent)
+        smallest = parent
+        smallest = left if left < @heap.size && @heap[left] < @heap[smallest]
+        smallest = right if right < @heap.size && @heap[right] < @heap[smallest]
+        return if smallest == parent
+
+        swap(parent, smallest)
+        sift_down(smallest)
+    end
+end
+
+
+
+class KthLargest
+
+=begin
+    :type k: Integer
+    :type nums: Integer[]
+=end
+    def initialize(k, nums)
+        raise ArgumentError, "k must be positive integer" if k <= 0
+        raise ArgumentError, "Initial array size is too small to determine the top #{k}" if k > nums.size + 1
+        @k = k
+        @top_k = MinHeap.new
+        nums.each { |num| add(num) }
+    end
+
+
+=begin
+    :type val: Integer
+    :rtype: Integer
+=end
+    def add(val)
+        if  @top_k.size < @k
+            @top_k.push(val)
+        elsif @top_k.peek < val
+            @top_k.pop
+            @top_k.push(val)
+        end
+        @top_k.peek
+    end
+end
+```
diff --git a/703/step4.md b/703/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正