LeetCode--Median of Two Sorted Arrays
#Median of Two Sorted Arrays
更多技术博客 http://vilins.top/
##题目
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)).
You may assume nums1 and nums2 cannot be both empty.
###Example
nums1 = [1, 3] nums2 = [2] The median is 2.0###Example
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5##分析
这题要求时间复杂度为O(log (m+n)).所以我们需要在遍历一次的一半时间内需要将结果找出来。而且我们不需要额外的申请空间，我们采取的策略是两个数组同时遍历，遍历的过程中同时比较元素的大小，这样我们就可以找出前O(log (m+n))个元素，然后就是我们需要寻找的结果。
##源码
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { int totalSize = nums1Size + nums2Size; int medianSize = totalSize/2; int a1 = 0, a2 = 0; double result = 0; int t = 1; //当第一个数组为空的时候，再分别讨论奇偶 if(nums1Size == 0) { if(totalSize%2 == 0) { int tag1,tag2; for(int i = 0; i <= medianSize; i++) { if(i == medianSize -1) { tag1 = nums2[i]; } if(i == medianSize) { tag2 = nums2[i]; } } return (double)(tag1+tag2)/2; } else { int tag1,tag2; for(int i = 0; i <= medianSize; i++) { if(i == medianSize) { tag1 = nums2[i]; } } return tag1; } } //当第二个数组为空的时候，再分别讨论奇偶 if(nums2Size == 0) { if(totalSize%2 == 0) { int tag1,tag2; for(int i = 0; i <= medianSize; i++) { if(i == medianSize -1) { tag1 = nums1[i]; } if(i == medianSize) { tag2 = nums1[i]; } } return (double)(tag1+tag2)/2; } else { int tag1,tag2; for(int i = 0; i <= medianSize; i++) { if(i == medianSize) { tag1 = nums1[i]; } } return tag1; } } if(totalSize%2 == 0) { int tag1 = 0, tag2 = 0; for(int i = 0; i <= medianSize; i++) { if((nums1[a1] <= nums2[a2])&&(a1 < nums1Size)||a2 == nums2Size) { if(i == medianSize - 1) { tag1 = nums1[a1]; } if(i == medianSize) { tag2 = nums1[a1]; } a1++; } else{ if(i == medianSize - 1) { tag1 = nums2[a2]; } if(i == medianSize) { tag2 = nums2[a2]; } a2++; } } //printf("%d\n", tag1); return (double)(tag1+tag2)/2; } else { int tag1 = 0; for(int i = 0; i <= medianSize; i++){ if((nums1[a1] <= nums2[a2])&&(a1 < nums1Size)||a2 == nums2Size) { if(i == medianSize ) { tag1 = nums1[a1]; } a1++; } else { if(i == medianSize) { tag1 = nums2[a2]; } a2++; } } return tag1; } }