叭叭一下如果某個(gè)cs門(mén)人焦慮了那那些學(xué)成男娘或禿頭的人一定會(huì)說(shuō)“什么你有時(shí)間焦慮”題目描述給定兩個(gè)大小分別為m和n的正序從小到大數(shù)組nums1和nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的中位數(shù)。算法的時(shí)間復(fù)雜度應(yīng)該為O(log (mn))。示例 1輸入nums1 [1,3], nums2 [2] 輸出2.00000 解釋合并數(shù)組 [1,2,3] 中位數(shù) 2示例 2輸入nums1 [1,2], nums2 [3,4] 輸出2.50000 解釋合并數(shù)組 [1,2,3,4] 中位數(shù) (2 3) / 2 2.5提示nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106分析要求求合并后的數(shù)組的中位數(shù)即使歸并也需要mn復(fù)雜度復(fù)雜度要求log(mn)需要結(jié)合折半的思想才行最小k值法:轉(zhuǎn)化為取第k小元素k為組合后長(zhǎng)度一半 每次遞歸淘汰一半元素 最后得到第k小元素思路1最小k值法OK兩數(shù)組長(zhǎng)度m n那么中位數(shù)在(m n 1) / 2 和(m n 2) / 2位置奇數(shù)個(gè)兩值相等偶數(shù)個(gè)為平均值那么怎么找到兩個(gè)值首先取k分別為這兩個(gè)值在兩個(gè)數(shù)組中分別取k/2位置比較兩個(gè)值對(duì)小的一個(gè)第k小元素肯定不在這個(gè)數(shù)組前k/2位置因?yàn)槿绻谶@里的話假設(shè)為x這一半最多k/2個(gè)小于等于x另一個(gè)數(shù)組最多k/2-1個(gè)小于等于x這樣最多k-1個(gè)小于等于x那x最多就是第k-1小的元素所以第k小元素不可能在這里。所以可以刪去這k/2個(gè)元素既然已經(jīng)刪去了比第k小元素小的k/2個(gè)元素那問(wèn)題轉(zhuǎn)化為求剩下元素的第k-k/2小元素這樣遞歸下去每次砍k/2的l次方元素直到k砍到為1直接取最小的那個(gè)就行了--這是一個(gè)遞歸退出條件。另一個(gè)遞歸退出條件是某個(gè)數(shù)組用盡直接在另一個(gè)數(shù)組取需要的值就行了。另外在比較的時(shí)候假如某個(gè)數(shù)組剩余長(zhǎng)度小于當(dāng)前k/2那就直接在另一個(gè)數(shù)組取要舍去的一半因?yàn)檫@一半已經(jīng)不夠舍去了(元素?cái)?shù)小于k/2)所以另一個(gè)數(shù)組小于第k的元素一定多于k/2(否則總數(shù)不夠k-1)。操作如下將問(wèn)題轉(zhuǎn)換為求兩個(gè)有序數(shù)組合并后的第k小元素其中k (mn1)/2和k (mn2)/2處理奇偶。定義函數(shù)getKth(nums1, start1, nums2, start2, k)若其中一個(gè)數(shù)組已經(jīng)用完直接返回另一個(gè)數(shù)組的當(dāng)前第 k 個(gè)元素。若 k 1返回兩個(gè)數(shù)組當(dāng)前起始位置的最小值。否則比較兩個(gè)數(shù)組的第k/2個(gè)元素若不夠則取最后一個(gè)剔除較小元素所在數(shù)組的前 k/2 個(gè)元素遞歸查找剩余部分。最終中位數(shù)為兩個(gè)k位置的平均值奇數(shù)時(shí)兩次相同。時(shí)間復(fù)雜度每次遞歸減少 k/2遞歸深度 log(mn)滿足要求。代碼如下class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length; int n nums2.length; int left (m n 1) / 2; int right (m n 2) / 2; return (getKth(nums1, 0, nums2, 0, left) getKth(nums1, 0, nums2, 0, right)) / 2.0; } public double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) { if(start1 nums1.length) return nums2[start2 k - 1]; if(start2 nums2.length) return nums1[start1 k - 1]; if(k 1) return Math.min(nums1[start1], nums2[start2]); int mid1 (start1 k / 2 - 1 nums1.length) ? nums1[start1 k / 2 - 1] : Integer.MAX_VALUE; int mid2 (start2 k / 2 - 1 nums2.length) ? nums2[start2 k / 2 - 1] : Integer.MAX_VALUE; if(mid1 mid2) { return getKth(nums1, start1 k / 2, nums2, start2, k - k / 2); } else { return getKth(nums1, start1, nums2, start2 k / 2, k - k / 2); } } }另外附上我的個(gè)人網(wǎng)站作分享交流大圣的技術(shù)空間 - 沉心礪骨 向陽(yáng)而生