南昌购物网站开发/今日军事新闻头条最新

最近面试，发现要手撕算法加上机试，被完败，索性给自己立一个目标，一周训练2次。

第一题。

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

这题力扣第四题，我看着简单，内容还可以一下子接受.想了快三个小时。

double get_mid(int* nums,int numsSize)
{if(numsSize%2){return nums[numsSize/2];}else{return (nums[numsSize/2]+nums[(numsSize)/2-1])*1.0/2;}
}double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {if((nums1Size==0)&&(nums2Size==0)) return 0;else if((nums1Size==0)&&(nums2Size!=0)){return get_mid(nums2,nums2Size);}else if((nums2Size==0)&&(nums1Size!=0)){return get_mid(nums1,nums1Size);}else{if(nums1[nums1Size-1] <=nums2[0]){int len = nums1Size+nums2Size ;int mid_index = len /2;if(len % 2 ) // 长度是奇数{if(mid_index >= nums1Size){return nums2[nums2Size-mid_index-1];}else{return nums1[mid_index]*1.0;}}else  //长度是偶数{if(mid_index < nums1Size){return (nums1[mid_index]+nums1[mid_index-1])*1.0/2;}else if((mid_index) == nums1Size){return (nums1[nums1Size-1]+nums2[0])*1.0/2;}else{return (nums2[nums2Size-mid_index-1]+nums2[nums2Size-mid_index])*1.0/2;}}}else if(nums2[nums2Size-1] <=nums1[0]){int len = nums1Size+nums2Size ;int mid_index = len /2;if(len % 2 ) //长度是奇数{if(mid_index >= nums2Size){return nums1[nums1Size-mid_index-1];}else{return nums2[mid_index];}}else //长度是偶数{if(mid_index < nums2Size){return (nums2[mid_index]+nums2[mid_index-1])*1.0/2;}else if((mid_index) == nums2Size){return (nums1[0]+nums2[nums2Size-1])*1.0/2;}else{return (nums1[nums1Size-mid_index-1]+nums1[nums1Size-mid_index])*1.0/2;}}}else{int len = nums1Size+nums2Size ;int mid_index = len /2;int count =0;int _n1 = 0,_n2=0;int last=0,midv=0;while(true){if(_n1 == nums1Size) {midv=nums2[_n2];count++;if(count == mid_index+1){if(len%2){return midv*1.0;}else{return (last+midv)*1.0/2;} }_n2++;last = midv;}else if(_n2 == nums2Size) {midv=nums1[_n1];count++;if(count == mid_index+1){if(len%2){return midv*1.0;}else{return (last+midv)*1.0/2;} }_n1++;last = midv;}else{if(nums1[_n1] >= nums2[_n2]){midv = nums2[_n2];count++;if(count == mid_index+1){if(len%2){return midv*1.0;}else{return (last+midv)*1.0/2;}}_n2++;last = midv;}else{midv = nums1[_n1];count++;if(count == mid_index+1){if(len%2){return midv;}else{return (last+midv)*1.0/2;}}_n1++;last = midv;}}}}}}

写的很烂很长，就是没有做过算法题目的人的思维，用了很多特殊情况来提高运算速度，其实把最后一个else提取出来也可以进行运算。但不知道为什么内存消耗很高。