寻找两个正序数组的中位数 #162

Activity

1. sisterAn

   added

   腾讯

   LeetCode

   虾皮

   on Mar 23, 2021
2. xiaoerwen commented on Mar 24, 2021

   

   xiaoerwen

   on Mar 24, 2021

   More actions

   const findMedianSortedArrays = (nums1, nums2) => {
       if (!nums1.length && !nums2.length) {
           return null;
       }
   
       // 如果数组1为空
       if (!nums1.length) {
           // 若此时数组2仅一个值，那么该值为中位数
           if (nums2.length === 1) {
               return nums2[0];
           }
   
           /** 
            * 否则比较数组2，取中位数
            * 比较单个数组采用二分法
            */
           let half = Math.floor(nums2.length / 2);
           return findMedianSortedArrays(nums2.slice(0, half), nums2.slice(half));
       }
   
       // 如果数组2为空，同理
       if (!nums2.length) {
           if (nums1.length === 1) {
               return nums1[0];
           }
   
           let half = Math.floor(nums1.length / 2);
           return findMedianSortedArrays(nums1.slice(0, half), nums1.slice(half));
       }
   
       // 如果两个数组都只剩1个数，取两者中间值
       if (nums1.length === 1 && nums2.length === 1) {
           return nums1[0] === nums2[0] ? nums1[0] : (nums1[0] + nums2[0]) / 2;
       }
   
       // 比较两个数组的最小值，丢弃最小值
       nums1[0] < nums2[0] ? nums1.shift() : nums2.shift();
   
       /**
        * 这里注意边界值，丢弃最小值后有的数组可能为空
        */
       if (!nums1.length) {
           // 强制丢掉最大值
           nums2.pop();
           return findMedianSortedArrays(nums1, nums2);
       }
       if (!nums2.length) {
           nums1.pop();
           return findMedianSortedArrays(nums1, nums2);
       }
   
       // 比较两个数组的最大值，丢弃最大值
       nums1[nums1.length - 1] > nums2[nums2.length - 1] ? nums1.pop() : nums2.pop();
       // 重复该操作
       return findMedianSortedArrays(nums1, nums2);
   };

   思路：比较两个有序数组的最小值与最大值，剔除最大最小值后重新比较
   重复此操作，直到剩余1个数，那么该数为中位数
   如果剩余2个数，那么中位数为两者和除2
   单数组采用二分法

   注意：边界值比较多

   该题耗时：20ms（击败了99%），内存消耗：41.9M（击败了94%）
3. Upting commented on Mar 24, 2021

   

   Upting

   on Mar 24, 2021

   Last edited by Upting

   More actions

   来个简单点的：

   const arr1 = [1, 2, 10];
   const arr2 = [2, 5, 7, 8];
   
   function findMiddleNumber(arr1, arr2) {
           // 容错处理
           if (!arr1.length && !arr2.length) return null;
   	// 合并并排序
   	const total = [...arr1, ...arr2].sort((a, b) => a - b);
   	// 中位数索引
   	let midIndex = (total.length - 1) / 2;
   
   	// 两位
   	if (String(midIndex).includes(".")) {
   		const left = parseInt(midIndex);
   		const right = parseInt(midIndex) + 1;
   		const midNumber = (total[left] + total[right]) / 2;
   		return midNumber.toFixed(5);
   	} else {
   		// 一位
   		return total[midIndex].toFixed(5);
   	}
   }
   
   console.log(findMiddleNumber(arr1, arr2));