地方门户网站系统,不同网站建设特点,wordpress 侧边栏位置,索牛网站建设最近面试#xff0c;发现要手撕算法加上机试#xff0c;被完败#xff0c;索性给自己立一个目标#xff0c;一周训练2次。
第一题。
给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
…最近面试发现要手撕算法加上机试被完败索性给自己立一个目标一周训练2次。
第一题。
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 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 mnums2.length n0 m 10000 n 10001 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((nums1Size0)(nums2Size0)) return 0;else if((nums1Size0)(nums2Size!0)){return get_mid(nums2,nums2Size);}else if((nums2Size0)(nums1Size!0)){return get_mid(nums1,nums1Size);}else{if(nums1[nums1Size-1] nums2[0]){int len nums1Sizenums2Size ;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 nums1Sizenums2Size ;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 nums1Sizenums2Size ;int mid_index len /2;int count 0;int _n1 0,_n20;int last0,midv0;while(true){if(_n1 nums1Size) {midvnums2[_n2];count;if(count mid_index1){if(len%2){return midv*1.0;}else{return (lastmidv)*1.0/2;} }_n2;last midv;}else if(_n2 nums2Size) {midvnums1[_n1];count;if(count mid_index1){if(len%2){return midv*1.0;}else{return (lastmidv)*1.0/2;} }_n1;last midv;}else{if(nums1[_n1] nums2[_n2]){midv nums2[_n2];count;if(count mid_index1){if(len%2){return midv*1.0;}else{return (lastmidv)*1.0/2;}}_n2;last midv;}else{midv nums1[_n1];count;if(count mid_index1){if(len%2){return midv;}else{return (lastmidv)*1.0/2;}}_n1;last midv;}}}}}}
写的很烂很长就是没有做过算法题目的人的思维用了很多特殊情况来提高运算速度其实把最后一个else提取出来也可以进行运算。但不知道为什么内存消耗很高。
