iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
0
自我挑戰組

有志者,事竟成。系列 第 10

Day10 第三十四題LeetCode #4 Median of Two Sorted Arrays

題目描述

給定兩個排好順序的vector
請輸出他們的中間數
並將計算時間卡在O(log(兩者長度和))

思維

寫一個新的vector,把兩個vector排進去再sort他,接著就按位置取中間數就行。

程式碼

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums3;
        double ans;
        nums3.insert(nums3.end(),nums1.begin(),nums1.end());
        nums3.insert(nums3.end(),nums2.begin(),nums2.end());
        sort(nums3.begin(),nums3.end());
        if(nums3.size()%2==1)
            ans=nums3[((nums3.size())-1)/2];
        else
        {
            ans=(nums3[(nums3.size())/2]+nums3[(nums3.size())/2-1])/2.0;
        }
        return ans;
    }
};

心路歷程

這題在Leetcode裡面屬於Hard的題目,所以原先我其實有點想要跳過.....
但還是按進去看了一下,發現其實並不是沒有想法,所以還是寫了。
原本看到O(log(n))還真的想說是不是要用二元法來跑,但可能腦袋一抽......
我就突然寫成這個版本,而且還覺得簡單易懂,而且這個方法雖然我是不知道多快啦,但是過了哈哈哈!
不過話說....自從我認識sort....我好像就沒在自己寫sort了→懶散的廢物


上一篇
Day9 第三十三題 LeetCode #3 Longest Substring Without Repeating Characters
下一篇
Day11 LeetCode #5 Longest Palindromic Substring
系列文
有志者,事竟成。19

尚未有邦友留言

立即登入留言