LeetCode 4. Median of Two Arrays

本文主要是介绍LeetCode 4. Median of Two Arrays，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4. Median of Two Arrays

一、问题描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

二、输入输出

Example 1:

nums1 = [1, 3]
nums2 = [2]The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]The median is (2 + 3)/2 = 2.5

三、解题思路

排序

• 把两个数组排序，形成一个有序的新数组，然后根据长度是奇数还是偶数返回对应的中位数。算法思路非常简单，但是复杂度O(m+n) 显然不符合题意。运行速度却击败了80%的提交，也是醉了。

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> total;int i = 0, j = 0;for (i = 0,j = 0; i < nums1.size() && j < nums2.size(); ){if(nums1[i] < nums2[j]){total.push_back(nums1[i]);i++;}else{total.push_back(nums2[j]);j++;}}if(i < nums1.size())total.insert(total.end(), nums1.begin()+i, nums1.end());if(j < nums2.size())total.insert(total.end(), nums2.begin()+j, nums2.end());int n = total.size();if(n % 2 != 0){return static_cast<double>(total[n/2]);}else{return static_cast<double>(total[n/2-1] + total[n/2]) / 2.0;}}
};

这篇关于LeetCode 4. Median of Two Arrays的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---