摘要:難度為這個(gè)題目描述很清晰給出兩個(gè)排序好的數(shù)組求這兩個(gè)數(shù)組的中位數(shù)在解這個(gè)題的過(guò)程中會(huì)碰到以下的問(wèn)題先合起來(lái)重新排序是不可行的時(shí)間復(fù)雜度太高為先歸并排序也是不可行的時(shí)間復(fù)雜度為用類似桶排的方法時(shí)間復(fù)雜度為不可行可能會(huì)碰到多種全部大于或全部小于
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
難度為Hard.
這個(gè)題目描述很清晰, 給出兩個(gè)排序好的數(shù)組, 求這兩個(gè)數(shù)組的中位數(shù). 在解這個(gè)題的過(guò)程中, 會(huì)碰到以下的問(wèn)題:
先合起來(lái)重新排序是不可行的, 時(shí)間復(fù)雜度太高, 為O((m+n)log(m+n))
先歸并排序也是不可行的, 時(shí)間復(fù)雜度為O(m+n)
用類似桶排的方法時(shí)間復(fù)雜度為O(m+n), 不可行
可能會(huì)碰到多種case, nums1全部大于或全部小于nums2(1,2,3 4,5,6), nums1和nums2交錯(cuò)(2,4,6 1,3,5), 最大最小都屬于其中一個(gè)序列(1,10 3,4,5), 等等
總數(shù)為奇數(shù)和偶數(shù)的處理可能會(huì)不太一樣
中位數(shù), 或者中位點(diǎn)旁邊的兩個(gè)數(shù), 可能都位于某個(gè)數(shù)組, 也可能各自分布在兩個(gè)數(shù)組中.
題目中給定的復(fù)雜度, 只能用二分查找的方法, 但是怎么在兩個(gè)數(shù)組上應(yīng)用呢? 我有兩種通過(guò)的方法.
第一種的思路是:
假定中位數(shù)兩邊的數(shù)是L, R. 對(duì)總數(shù)為奇數(shù)的情況, L=R.
假定L或者R在nums1中, 按二分查找定位.
二分查找的中點(diǎn)游標(biāo)為P, 在nums1中, 我們知道比P小, 比P大的有多少, 我們還需要知道, 在nums2中, P處于什么位置
給定P, 在nums2中二分查找, 找到比P大, 比P小的元素?cái)?shù)目.
這樣在兩個(gè)數(shù)組中, 比P大的數(shù)目n1和比P小的數(shù)目n2就確定了.
我們可以調(diào)整P的位置, 直到找到L和R的值為止
由于L和R可能位于nums1或者nums2中, 所以還需要假定L或R在nums2中的情況再做一次. 同樣有些細(xì)節(jié)問(wèn)題需要解決.
最終程序如下:
public class Solution { /** * AC Time Complexity: O(logm*logn) */ public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1 = nums1.length; int l2 = nums2.length; if (l1 == 0) { if (l2 % 2 == 1) { return nums2[l2 / 2]; } else { return ((double) nums2[l2 / 2] + nums2[l2 / 2 - 1]) / 2; } } if (l2 == 0) { if (l1 % 2 == 1) { return nums1[l1 / 2]; } else { return ((double) nums1[l1 / 2] + nums1[l1 / 2 - 1]) / 2; } } ListretList = new ArrayList (); getMidLR(nums1, nums2, retList); getMidLR(nums2, nums1, retList); if (retList.size() == 0) { if (l2 % 2 == 1) { return nums2[l2 / 2]; } else { return ((double) nums2[l2 / 2] + nums2[l2 / 2 - 1]) / 2; } } Integer sum = 0; for (Integer r : retList) { sum += r; } return (double) sum / retList.size(); } public void getMidLR(int[] nums1, int[] nums2, List ret) { Integer midL = null; Integer midR = null; int m = nums1.length; int n = nums2.length; int l = 0; int r = m - 1; int p = m / 2; while (true) { int numSmall = 0; int numBig = 0; int tl = 0; int tr = n - 1; int tp = n / 2; int curVal = nums1[p]; while (true) { if (tp == 0) { if (nums2[0] > curVal) { numSmall = 0; numBig = n; break; } else if (nums2[0] == curVal) { numSmall = 0; numBig = n - 1; break; } } if (tp == n - 1) { if (nums2[n - 1] < curVal) { numSmall = n; numBig = 0; break; } else if (nums2[n - 1] == curVal) { numSmall = n - 1; numBig = 0; break; } } if (nums2[tp] == curVal) { numSmall = tp; numBig = n - tp - 1; break; } if (nums2[tp] < curVal && curVal < nums2[tp + 1]) { numSmall = tp + 1; numBig = n - tp - 1; break; } if (tl == tr) { break; } if (nums2[tp] > curVal) { // tp move left tr = tp; tp = (tl + tr) / 2; } else { // tp move right tl = tp; tp = (tl + tr) / 2; if (tl == tp && tl < tr) { tl++; tp++; } } }// end inner while int s = numSmall + p; int b = numBig + m - p - 1; if (s == b) { midL = midR = curVal; break; } if (s == (b + 1)) { midR = curVal; } else if ((s + 1) == b) { midL = curVal; } if (midL != null && midR != null) { break; } // move p if (l == r) { break; } if (s > b) { // p move left r = p; p = (l + r) / 2; } else { // p move right l = p; p = (l + r) / 2; if (l == p && l < r) { l++; p++; } } } if (midL != null) { ret.add(midL); } if (midR != null) { ret.add(midR); } } public static void main(String[] args) { Solution s = new Solution(); int[] nums11 = { 1, 3 }; int[] nums12 = { 2 }; System.out.println(s.findMedianSortedArrays(nums12, nums11)); int[] nums21 = { 1, 2 }; int[] nums22 = { 3, 4 }; System.out.println(s.findMedianSortedArrays(nums22, nums21)); int[] nums31 = { 1, 2, 3 }; int[] nums32 = { 3, 4 }; System.out.println(s.findMedianSortedArrays(nums32, nums31)); int[] nums41 = {}; int[] nums42 = { 1 }; System.out.println(s.findMedianSortedArrays(nums41, nums42)); int[] nums51 = { 1, 2 }; int[] nums52 = { 1, 2 }; System.out.println(s.findMedianSortedArrays(nums51, nums52)); } }
但問(wèn)題是, 這個(gè)算法的時(shí)間復(fù)雜度是O(logm*logn), 雖然能AC, 但比題目中要求的O(log(m+n))要高.
這里還有第二種解法:
因?yàn)槿绻謩e做二分的話, 必然會(huì)是O(logm*logn)的復(fù)雜度, 要達(dá)到題目中要求的復(fù)雜度, 需要兩個(gè)數(shù)組一起做二分.
如下實(shí)現(xiàn)一個(gè)方法找兩個(gè)數(shù)組中第n大的數(shù):
假定需要找nums1的下標(biāo)(s1,e1)范圍內(nèi)nums2的下標(biāo)(s2,e2)范圍內(nèi)的第n個(gè)大小的數(shù), 我們先把nums1和nums2各自的中點(diǎn)p1, p2 找出:
假定p1元素>=p2元素, 否則把nums1和nums2交換位置.
對(duì)于圖中黃色的部分, 即s1~p1, s2~p2, 肯定是小于等于p1元素的, 這兩塊元素的數(shù)目可以求出, 定義為lmargin, 如果nth<=lmargin, 那么第nth元素必然小于p1元素, p1右邊的元素可以拋棄.
問(wèn)題就變成找上圖的第nth元素
同樣的, 依照類似的想法,
如果p1~e1, p2~e2這兩部分元素的數(shù)目, 大于(元素總數(shù)-nth), 這就說(shuō)明, 第nth元素, 是大于p2元素的. p2以前這塊, s2~p2是可以被拋棄的.
問(wèn)題就變成, 找上圖的第nth - (p2 - s2) 個(gè)元素.
如此可以迭代下去, 到其中一對(duì)游標(biāo)相遇的時(shí)候, 就很好解決了.
如上, 找到第n大的數(shù), 問(wèn)題就等于是解決了. 可以順利找到中位數(shù).
基本思路是這樣, 還有些細(xì)節(jié)問(wèn)題需要解決.
AC的代碼如下:
public class Solution2 { /** * AC Time Complexity: O(log(m+n)) */ public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1 = nums1.length; int l2 = nums2.length; // judge for empty conditions if (l1 == 0) { if (l2 % 2 == 1) { return nums2[l2 / 2]; } else { return ((double) nums2[l2 / 2] + nums2[l2 / 2 - 1]) / 2; } } if (l2 == 0) { if (l1 % 2 == 1) { return nums1[l1 / 2]; } else { return ((double) nums1[l1 / 2] + nums1[l1 / 2 - 1]) / 2; } } boolean isOdd = (l1 + l2) % 2 == 1; if (isOdd) { // if odd, just return the center one return findNth(nums1, 0, l1 - 1, nums2, 0, l2 - 1, (l1 + l2) / 2 + 1); } else { // if even, return the average of the center two return ((double) findNth(nums1, 0, l1 - 1, nums2, 0, l2 - 1, (l1 + l2) / 2) + (double) findNth(nums1, 0, l1 - 1, nums2, 0, l2 - 1, (l1 + l2) / 2 + 1)) / 2; } } public int findNth(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, int nth) { // if one or two array indexes are trapped to one element if (s1 == e1) { if (s2 == e2) { return nth == 1 ? Math.min(nums1[s1], nums2[s2]) : Math.max(nums1[s1], nums2[s2]); } int nval = nums2[nth + s2 - 1]; if (nval <= nums1[s1]) { return nval; } else { return Math.max(nums1[s1], nums2[nth + s2 - 2]); } } // the other trapped condition, rotate to do as the above if (s2 == e2) { return findNth(nums2, s2, e2, nums1, s1, e1, nth); } int p1 = (s1 + e1) / 2; int p2 = (s2 + e2) / 2; if (nums1[p1] >= nums2[p2]) { boolean f1 = false; boolean f2 = false; // number of all elements before p1(in nums1) or p2(in nums2) // under condition nums1[p1]>=nums2[p2], // all of theses elements are smaller or equal than nums1[p1] int lmargin = p1 - s1 + 1 + p2 - s2 + 1; // new indexes int ns1 = s1; int ne1 = e1; int ns2 = s2; int ne2 = e2; int nnth = nth; // if nth0) { // nums1: the right of p1(including) can be discarded ne1 = p1 - 1; f1 = true; } else if (nth <= lmargin) { // nums1: the right of p1(excluding) can be discarded ne1 = p1; f1 = true; } // number of all elements after p1(in nums1) or p2(in nums2) // under condition nums1[p1]>=nums2[p2], // all of theses elements are greater or equal than nums2[p2] int rmargin = e1 - p1 + 1 + e2 - p2 + 1; // we are finding the nth element from the beginning as well as rnth // element from the end of the two int rnth = e1 - s1 + 1 + e2 - s2 + 1 - nth + 1; // if rnth rnth && e2 > p2) { // nums2: the left of p2(including) can be discarded nnth = nth - (p2 - s2) - 1; ns2 = p2 + 1; f2 = true; } else if (rmargin >= rnth) { // nums2: the left of p2(excluding) can be discarded nnth = nth - (p2 - s2); ns2 = p2; f2 = true; } if (f1 || f2) { // something changes, go on with the new index return findNth(nums1, ns1, ne1, nums2, ns2, ne2, nnth); } } // else reverse and find return findNth(nums2, s2, e2, nums1, s1, e1, nth); } }
這個(gè)算法的時(shí)間復(fù)雜度可以認(rèn)為是O(log(m+n)).
但其實(shí), 我對(duì)這兩個(gè)算法都不太滿意, 都比較冗長(zhǎng)復(fù)雜, 暫時(shí)還沒(méi)有想到更簡(jiǎn)潔, 效率更高的算法.
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/66413.html
摘要:解法解法應(yīng)該是最常見(jiàn)的一種解法,就是將兩個(gè)數(shù)組頭尾相加合并起來(lái),然后重新排序,例如輸入兩個(gè)數(shù)組,合并之后變?yōu)椋缓笄蟪鲋形粩?shù)。如果兩個(gè)數(shù)組長(zhǎng)度和為偶數(shù),那么中位數(shù)有兩個(gè),否則只有一個(gè) 題目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...
摘要:最新解法及思路有兩個(gè)有序數(shù)組和,他們的大小各是和,請(qǐng)找出這兩個(gè)數(shù)組所有數(shù)的中位數(shù),總得時(shí)間復(fù)雜度不超過(guò)歸并計(jì)數(shù)法復(fù)雜度時(shí)間空間思路如果對(duì)時(shí)間復(fù)雜度沒(méi)有要求,這個(gè)方法是實(shí)現(xiàn)起來(lái)最簡(jiǎn)單的,我們只需要從下往上依次數(shù)個(gè)元素即可。 Median of Two Sorted Arrays 最新解法及思路:https://yanjia.li/zh/2018/11/... There are two...
摘要:復(fù)雜度思路因?yàn)橐抑形粩?shù),又是在兩個(gè)的數(shù)組里面。所以考慮用二分法。二分法經(jīng)常適合的接下來(lái)考慮如何二分。然后對(duì)和進(jìn)行比較,記為和。所以為了縮小搜索范圍,我們可以扔掉這些數(shù),在的剩下來(lái)的數(shù)中和的數(shù)組中接著找。說(shuō)明中沒(méi)有個(gè)數(shù)可以尋找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...
摘要:由于要求的時(shí)間,所以選擇二分法。思路是找到兩個(gè)數(shù)組合并起來(lái)的第個(gè)元素。這樣只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素,代入功能函數(shù)即可。據(jù)此,根據(jù)二分法的性質(zhì),我們?cè)谶f歸時(shí)可以將前即個(gè)元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...
摘要:自第一篇收集向的文章發(fā)布后,近年半沒(méi)更新這個(gè)專欄了。今天是分類中第一個(gè)的,叫做。不過(guò)這樣需要兩個(gè)數(shù)組各掃一遍,然而我們的目的只是要取到中間值,似乎并不用完整的掃一遍。那么也就意味著,我們最終要記錄的值可能是兩個(gè)。 大家好,我叫張小豬。 自第一篇收集向的文章發(fā)布后,近 1 年半沒(méi)更新這個(gè)專欄了。最近面試中發(fā)現(xiàn)將近 60% 的候選人對(duì)于 bubble sort 面露難色,于是心悸于自己也忘...
閱讀 3724·2021-10-13 09:39
閱讀 3789·2021-09-24 09:48
閱讀 1189·2021-09-01 10:30
閱讀 2526·2019-08-30 15:55
閱讀 1774·2019-08-29 16:39
閱讀 2296·2019-08-26 13:55
閱讀 3050·2019-08-26 12:23
閱讀 1634·2019-08-26 11:59