刷题4. Median of Two Sorted Arrays

一、题目

Median of Two Sorted Arrays,具体请自行搜索。

这个题目,我看了一下,经过一番思考,我觉得实现起来不是很复杂。

但要做到bug free也不难,最大的问题是性能问题。

性能只有42%的样子,内存占用太多。还需要进一步优化!!!

刷题4. Median of Two Sorted Arrays

二、这个题目,我自己实现

提交了2次:

第1次: Wrong Answer

第2次:终于对了

下面是我的完整代码实现,需要的拿去:

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        float f = 0;
        vector<int> res;
        int i=0,j=0;
        while(i<m && j<n){
            if(nums1[i]<nums2[j]){
                res.push_back(nums1[i]);
                i++;
            }else{
                res.push_back(nums2[j]);
                j++;
            }
        }
        while(i<m){
            res.push_back(nums1[i]);
            i++;
        }
        while(j<n){
           res.push_back(nums2[j]);
           j++; 
        }
            
        if((m+n) %2 == 0){
            //总共有偶数个,取中间2个平均值
            f = res[(m+n)/2-1]+res[(m+n)/2];
            return f/2;
        }else{
            //找到中间值
            return res[(m+n)/2];
        }
    }
};

int main(){
    vector<int> v1 = {1,3};
    vector<int> v2 = {2};
    Solution s;
    cout<<s.findMedianSortedArrays(v1,v2)<<endl;
    
    v1 = {1,2};
    v2 = {3,4};
    cout<<s.findMedianSortedArrays(v1,v2)<<endl;
    return 0;
}

三、改进

我先思考一下...

上一篇:c-在容器中使用n_th元素,但使用另一个键


下一篇:c – 2D CUDA中值滤波器优化