LeetCode算法笔记–Day17
4. 寻找两个正序数组的中位数
题目:
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例1:
输入: nums1 = [1, 2],nums2 = [3, 4]
输出:2.5
我的解答:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
var findMedianSortedArrays = function(nums1, nums2) { let _len1 = nums1.length; let _len2 = nums2.length; let _combineArr = []; let _p1 = 0; let _p2 = 0;
if(_len1 == 0 || _len2 == 0){ return _len1 == 0 ? getMedianNum(nums2) : getMedianNum(nums1); }else{ while(_p1 < _len1 || _p2 < _len2){
if(typeof nums1[_p1] == "undefined"){ _combineArr = _combineArr.concat(nums2.splice(_p2)) return getMedianNum(_combineArr) } else if(typeof nums2[_p2] == "undefined"){ _combineArr = _combineArr.concat(nums1.splice(_p1)) return getMedianNum(_combineArr) } else{ if(nums1[_p1] < nums2[_p2]){ _combineArr.push(nums1[_p1]); _p1 += 1; }else{ _combineArr.push(nums2[_p2]); _p2 += 1; } } } } };
var getMedianNum = function(nums){ let _len = nums.length; return _len%2==0 ? ((nums[_len/2-1]+nums[_len/2])/2).toFixed(1) : nums[Math.floor(_len/2)].toFixed(1); }
|