やめられないやめられない

3日坊主、先送り～

LeetCode - 4. Median of Two Sorted Arraysを解く

leetcode ruby

３日坊主を乗り切るんだ！

問題へのリンク

https://leetcode.com/problems/median-of-two-sorted-arrays/

問題を解く前に

中央値について一部誤解していたみたい。数字が偶数個の場合は算術平均を取るのだった。

log(n) は 2の対数ということで、計算量O(log (m+n))ということはm+nが16なら2の4乗だから4ループで処理できるようにということか。

解き方を考えてみる

計算量の制約があるので、半分に切っていくようなやり方がよさそう。これはバイナリサーチ（2分探索）という方法。 しかし配列が2つあるので単純に処理する方法が思いつかない。例えば[1,2,3,4], [5,6,7,8]のような配列の場合はどう考えればいいんだろう？
わからずじまいなので、とりあえずリニアサーチ（線形探索）で処理するコードを書いた。

解答
# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Float}
def find_median_sorted_arrays(nums1, nums2)
    total_size = nums1.size + nums2.size
    
    is_even = total_size % 2 == 0 ? true : false
    if is_even
        medium_index = total_size / 2
    else
        medium_index = total_size / 2 + 1
    end
    
    count = 0
    index1 = 0
    index2 = 0
    medium = 0
    tmp = 0
    while count <= medium_index do
        if nums1.size == index1
            tmp = nums2[index2]
            index2 = index2 + 1
        elsif nums2.size == index2
            tmp = nums1[index1]
            index1 = index1 + 1
        elsif nums1[index1] > nums2[index2]
            tmp = nums2[index2]
            index2 = index2 + 1
        else
            tmp = nums1[index1]
            index1 = index1 + 1
        end
        count = count + 1
        
        if count == medium_index
            if is_even
                if nums1.size == index1
                    medium = (tmp.to_f + nums2[index2].to_f) / 2
                elsif nums2.size == index2
                    medium = (tmp.to_f + nums1[index1].to_f) / 2
                elsif nums1[index1] > nums2[index2]
                    medium = (tmp.to_f + nums2[index2].to_f) / 2
                else
                    medium = (tmp.to_f + nums1[index1].to_f) / 2
                end
            else
                medium = tmp.to_f
            end
        end
    end
    return medium
end

解説の理解と正解の写経は後日やろう。