文章目錄

• 題目描述
• 思路 & 代碼

題目描述

• 算是拖了好久的題目= =，一開始刷的時(shí)候沒打算直接沖困難
• 不過面試常客了，還是得沖掉，而且不能留下心魔嘛！
• 難點(diǎn)在于實(shí)現(xiàn)時(shí)間復(fù)雜度 O(log(m + n))，顯而易見得用二分法
  
  

思路 & 代碼

• 長度奇偶情況處理：因?yàn)榕紨?shù)要取平均值，所以這邊進(jìn)行了兩次函數(shù)調(diào)用，分別取較小、較大的中位數(shù)再取平均（奇數(shù)就相當(dāng)于跑重復(fù)了一次）
• 主要思路：基于二分法的基礎(chǔ)上進(jìn)行排除法
• 兩數(shù)組元素都夠的情況，每次舍去 k / 2 個(gè)數(shù)
• 一方不夠的情況，直接指向數(shù)組尾，看對比情況舍
• 保證空數(shù)組一定是 nums1[ ]
• 證明 & 更多見代碼注釋
• 注意：k 并非下標(biāo)

class Solution {/*** 正確性證明：每次去掉的值都是應(yīng)當(dāng)去掉的* 因?yàn)?#xff1a;答案一定不在數(shù)組n去掉范圍中，極端情況下也是在數(shù)組m范圍的尾部* 核心：排除法，不斷去掉可去值，并維護(hù)k(中位數(shù)為第k小數(shù))* ps：其實(shí)有效代碼只有 20 行= =*/public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;// +1 +2：k 不是下標(biāo)，比如 k = 1，指第一個(gè)，也就是 index + k - 1// left & right 是為了奇偶// 奇數(shù)情況 left == right// 偶數(shù)情況 left == right - 1int left = (n + m + 1) / 2;int right = (n + m + 2) / 2;// 奇數(shù)情況：兩次一樣的過程// 偶數(shù)情況：中間倆個(gè)值的平均值return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left)+ getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) / 2.0;}int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;// 保證空數(shù)組一定是 nums1[]if(len1 > len2){return getKth(nums2, start2, end2, nums1, start1, end1, k);}// 出現(xiàn)空數(shù)組，直接化成求一數(shù)組第k小數(shù)的情況if(len1 == 0){return nums2[start2 + k - 1];}// 找到最后的情況，直接返回兩數(shù)組當(dāng)前最小值if(k == 1){return Math.min(nums1[start1], nums2[start2]);}// 指向第k/2小的位置 or 指向尾部int i = start1 + Math.min(len1, k / 2) - 1;int j = start2 + Math.min(len2, k / 2) - 1;// 舍去值的數(shù)量不一定相等（指向尾部情況）// 舍nums2的情況if(nums1[i] > nums2[j]){return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));}// 舍nums1的情況else{return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));}}}

• 無注釋版

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int mid1 = (nums1.length + nums2.length + 1) / 2;int mid2 = (nums1.length + nums2.length + 2) / 2;return (getMid(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, mid1) + getMid(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, mid2)) / 2.0;}public int getMid(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;if(len2 < len1) {return getMid(nums2, start2, end2, nums1, start1, end1, k);}if(len1 == 0) {return nums2[start2 + k - 1];}if(k == 1) {return Math.min(nums1[start1], nums2[start2]);}int index1 = start1 + Math.min(len1, k / 2) - 1;int index2 = start2 + Math.min(len2, k / 2) - 1;if(nums1[index1] < nums2[index2]) {return getMid(nums1, index1 + 1, end1, nums2, start2, end2, k - (index1 - start1 + 1));}else {return getMid(nums1, start1, end1, nums2, index2 + 1, end2, k - (index2 - start2 + 1));}} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】4. 寻找两个正序数组的中位数（Java、二分、递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。