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 (mn)).You may assume nums1 and nums2 cannot be both empty.###Examplenums1 [1, 3] nums2 [2] The median is 2.0###Examplenums1 [1, 2] nums2 [3, 4] The median is (2 3)/2 2.5##分析这题要求时间复杂度为O(log (mn)).所以我们需要在遍历一次的一半时间内需要将结果找出来。而且我们不需要额外的申请空间我们采取的策略是两个数组同时遍历遍历的过程中同时比较元素的大小这样我们就可以找出前O(log (mn))个元素然后就是我们需要寻找的结果。##源码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)(tag1tag2)/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)(tag1tag2)/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)(tag1tag2)/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; } }更多技术博客 http://vilins.top/