leetcode题解日练--2016.9.17

本文主要是介绍leetcode题解日练--2016.9.17，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

平常心

今日题目：

1、两个有序数组的中位数

2、找到两个数组中最小的k对最小和

今日摘录：

天上浮云如白衣，斯须改变如苍狗。——杜甫《何叹》

4. Median of Two Sorted Arrays | Difficulty: Hard

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

tag：数组|二分|分治
题意：先给定两个数组，求它们的中位数，复杂度O(log (m+n)).

思路：
1、找中位数就是在两个数组中各自找到一个i、j元素作为分割线，分割线需要满足三个方程：
i+j=(nums1.size()+nums2.size()+1)/2 —> 二分去搜索i.j=(nums1.size()+nums2.size()+1)/2-i
nums1[i-1]<=nums2[j] (前提i-1和j不越界)
nums2[j-1]<=nums1[i] （前提j-1和i不越界）
当找到满足条件的i，j时候就返回，
否则如果nums1[i-1]

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size(),len2 = nums2.size();if(len1>len2)   return findMedianSortedArrays(nums2,nums1);int halfLen = (len1+len2+1)/2;int iLeft = 0,iRight = len1;double maxLeft = INT_MIN,minRight = INT_MAX;while(iLeft<=iRight){int i = iLeft+(iRight-iLeft)/2;int j = halfLen-i;if(j>

这篇关于leetcode题解日练--2016.9.17的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---