給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請你找出這兩個有序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會同時為空。示例 1:
nums1 = [1, 3]
nums2 = [2]
?
則中位數(shù)是 2.0示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
?
則中位數(shù)是 (2 + 3)/2 = 2.5

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

第四題，這次難度是困難，這是我們第一次遇到困難。

我們遇到什么困難也不要怕，微笑著面對它！ 消除恐懼的最好辦法就是面對恐懼！ 加油！奧利給！

呃，串戲了

回正題，老規(guī)矩先看題干構(gòu)建函數(shù)頭，給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2，輸入為兩個有序數(shù)組即 int[] nums1 和 int[] nums2 。請你找出這兩個有序數(shù)組的中位數(shù)，那返回值是一個 double (因?yàn)橹形粩?shù)肯能是兩個數(shù)的平均值，所以會有小數(shù)位)。

public double FindMedianSortedArrays(int[] nums1, int[] nums2)

再接著讀題，要求算法的時間復(fù)雜度為 O(log(m + n))。這里問題就來了，求兩個數(shù)組的中位數(shù)不難，只要將兩個數(shù)組合并，即可很容易的找出其中位數(shù)，但是要求時間復(fù)雜度是 O(log(m + n)) 又是什么鬼。時間復(fù)雜度我們知道是標(biāo)識算法運(yùn)算n時常與輸入變量的長度相關(guān)性的標(biāo)志，常見的包括 O(1)常數(shù)時間 O(n)線性時間 O(logn)對數(shù)時間 等。

題目要求我們時間復(fù)雜度為 O(log(m+n))就是要求算法為對數(shù)時間，而常見的對數(shù)時間的算法有，二分查找和一些二叉樹的操作。這就是直接給了我們答案有木有?？磥硎且獙?shù)據(jù)進(jìn)行一個二分查找的改造了（這里肯定不是二叉樹，因?yàn)闃?gòu)建二叉樹的算法復(fù)雜度已經(jīng)是O(m+n)了）。

我們來看二分查找算法的百度百科定義，二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

嗯，順序存儲結(jié)構(gòu)，咱們的兩個數(shù)組都是有序的，這很好，二分查找的過程即為查找中間值，比較大小，如相等則是要找的值，如不相等再去相應(yīng)的子表中再次進(jìn)二分查找。這里我給出百度百科中的C#二分查找源碼。

public static int Method(int[] nums, int low, int high, int target) {while (low <= high){int middle = (low + high) / 2;if (target == nums[middle]){return middle;}else if (target > nums[middle]){low = middle + 1;}else if (target < nums[middle]){high = middle - 1;}}return -1; }

那么我們需要找的是什么，中位數(shù)，再次引用百度百科定義中位數(shù)（Median）又稱中值，統(tǒng)計學(xué)中的專有名詞，是按順序排列的一組數(shù)據(jù)中居于中間位置的數(shù)，代表一個樣本、種群或概率分布中的一個數(shù)值，其可將數(shù)值集合劃分為相等的上下兩部分。對于有限的數(shù)集，可以通過把所有觀察值高低排序后找出正中間的一個作為中位數(shù)。如果觀察值有偶數(shù)個，通常取最中間的兩個數(shù)值的平均數(shù)作為中位數(shù)。 所以我們要找的不是一個特定的值，而是一個存在于特定位置的數(shù)。所以我們只要找到特定位置上數(shù)是多少就好了。

首先我們有兩條數(shù)組，假設(shè) 我們合并兩條數(shù)組 nums1 nums2 = nums,那么位于 a 位置的中位數(shù) 將其分為兩部分即nums[0~(a-1)] 與 nums[a~(nums.Lenght-1)] ,且s兩部分的長度相同。我們設(shè)這兩部分為numsLeft 與 numsRight，那么numsLeft中應(yīng)包含 nums1的一部分與nums2的一部分，我們可以認(rèn)為 numsLeft = nums1[0~(i-1)] + nums2[0~(j-1)],那么 numsRight = nums1[i~(nums1.Lenght-1)] + nums2[j~(nums2.Lenght-1)]，這個是我們要達(dá)成的目標(biāo)。并且我們可以知道 Max(numsLeft)<=Min(numsRight) ，這便是我們的判斷標(biāo)準(zhǔn)。

那么看下具體的代碼實(shí)現(xiàn)吧

public double FindMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.Length > nums2.Length)//主操作放在長的數(shù)組上可以減少大多數(shù)情況下的算法耗時{ int[] temp = nums1;nums1 = nums2;nums2 = temp;}int minI = 0; //i 所處位置可能的最小值int maxI = nums1.Length; //i 所處位置可能的最大值int halfLen = (nums1.Length + nums2.Length + 1) / 2;//i的一半長度 由于int計算小數(shù)部分會被完全舍去，所以+1之后再除可以適應(yīng)奇偶問題while (minI <= maxI){int i = (minI + maxI) / 2; //在可能的范圍內(nèi)用二分查找法來找到正確的數(shù)值，這個是中間值int j = halfLen - i; //找到nums2 放入numsLeft中的最大值的位置if (i < maxI && nums2[j - 1] > nums1[i]) //判斷nums2 放入 numsLeft 中的最大值是否大于 nums1 放入numsRight 中的最小值{minI = i + 1; // i 這個中間值小了，我們調(diào)整 i 的范圍}else if (i > minI && nums1[i - 1] > nums2[j])//判斷nums2 放入 numsRight 中的最小值是否小于 nums1 放入numsLeft 中的最大值{maxI = i - 1; // i 這個中間值大了，我們調(diào)整 i 的范圍}else //i值是正確的值{int maxLeft; //找到左側(cè)最大值if (i == 0){maxLeft = nums2[j - 1]; }else if (j == 0) {maxLeft = nums1[i - 1]; }else {maxLeft = Math.Max(nums1[i - 1], nums2[j - 1]); }if ((nums1.Length + nums2.Length) % 2 == 1) { return maxLeft; } ?int minRight; //找到右側(cè)最小值if (i == nums1.Length) {minRight = nums2[j]; }else if (j == nums2.Length) {minRight = nums1[i]; }else { minRight = Math.Min(nums2[j], nums1[i]); } ?return (maxLeft + minRight) / 2.0;}}return 0.0; }

跑一下

執(zhí)行用時 :128 ms, 在所有 C# 提交中擊敗了99.21%的用戶

內(nèi)存消耗 :26.9 MB, 在所有 C# 提交中擊敗了5.05%的用戶

效率不錯。這個代碼我原來自己寫的比較亂，講起來比較麻煩我又參考了LeetCode官方給出的答案進(jìn)行了少許的修改。我們學(xué)習(xí)就是這樣，自己不會的有好的指導(dǎo)就應(yīng)該去學(xué)，學(xué)習(xí)永遠(yuǎn)是最值得驕傲的。

好了，這是我第一次講解困難難度的題目，有不清楚的地方大家可以在留言里提出，我會盡量給大家回復(fù)并講解清楚的。那么就讓我們一起努力吧！

想了解更多，掃碼關(guān)注我的公眾號 IP的dotNet吧

總結(jié)

以上是生活随笔為你收集整理的return两个返回值_LeetCode 第四题 寻找两个有序数组的中位数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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