您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java怎么尋找兩個(gè)有序數(shù)組的中位數(shù)”,在日常操作中,相信很多人在Java怎么尋找兩個(gè)有序數(shù)組的中位數(shù)問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對(duì)大家解答”Java怎么尋找兩個(gè)有序數(shù)組的中位數(shù)”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
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
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2 。
請(qǐng)找出這兩個(gè)有序數(shù)組的中位數(shù)。要求算法的時(shí)間復(fù)雜度為 O(log (m+n)) 。
1.自己的想法是 一共m + n 個(gè),我們可以新建一個(gè)List 然后每把最小的數(shù)放進(jìn)去,代碼如下:
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ leng = len(nums1) + len(nums2) tmpLen = leng//2 + 1 newList = [0]*tmpLen i = 0 j = 0 for k in range(tmpLen): if i == len(nums1): newList[k] = nums2[j] j += 1 elif j == len(nums2): newList[k] = nums1[i] i += 1 else: if nums1[i] < nums2[j]: newList[k] = nums1[i] i += 1 else: newList[k] = nums2[j] j += 1 if leng %2 == 0: return (newList[tmpLen - 2] + newList[tmpLen - 1])/2 else: return newList[tmpLen - 1]
2.類似與折半查找的思路,
由于題目要求的時(shí)間復(fù)雜度是(log(m+n)),如果我們直接把兩個(gè)數(shù)組整合一起,那么時(shí)間復(fù)雜度肯定超過(log(m+n))。所以整理肯定是不行的。那么還有什么方法嗎?答案是肯定的。
首先我們要先了解中位數(shù)的概念,中位數(shù)就是有序數(shù)組的中間那個(gè)數(shù)。那么如果我們將比中位數(shù)小的數(shù)和比中位數(shù)大的數(shù)去掉同樣的個(gè)數(shù),中位數(shù)的值也不會(huì)變化(數(shù)組的個(gè)數(shù)為偶數(shù)的時(shí)候另外討論,因?yàn)槟菚r(shí)候中位數(shù)是中間兩個(gè)數(shù)的平均值,所以中位數(shù)旁邊兩個(gè)數(shù)不能去掉)。
所以我們不妨試著將數(shù)組長度不斷縮短。這里不妨提出一個(gè)引理。假設(shè)有兩個(gè)有序數(shù)組am,bn,他們整合后的有序數(shù)組為cn+m。他們的中位數(shù)分別是Am/2,Bn/2,C(m+n)/2。如果Am/2 < Bn/2,則 A0…m/2 <= C(m+n)/2 <= Bn/2…n 。
引理證明:
假設(shè) Am/2 > C(m+n)/2 ,那么 Bn/2 > C(m+n)/2,所以在數(shù)組Am里有大于m/2個(gè)數(shù)大于C(m+n)/2,在數(shù)組Bn里也有n/2個(gè)數(shù)大于C(m+n)/2
也就是說在Cn+m里有(m+n)/2個(gè)數(shù)大于C(m+n)/2,此時(shí)就C(m+n)/2不再是數(shù)組Cn+m的中位數(shù)。
所以A0…m/2 <= C(m+n)/2。
同理可得C(m+n)/2 <= Cn/2…n 。
根據(jù)上述引理,我們不妨設(shè)m>n,那么我們根據(jù)判斷兩個(gè)數(shù)組的中位數(shù)大小,每個(gè)數(shù)組每次減少n/2長度,直到n為1。如此,我們通過減少log(n)次可以得到答案。這種方法的時(shí)間復(fù)雜度是(log(min(m,n)))。
class Solution: def getMedian(self,nums): size = len(nums) if size == 0: return [0,0] if size % 2 == 1: return [nums[size//2],size//2] else: return [(nums[size//2 - 1] + nums[size//2])/2,size//2] def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ size1 = len(nums1) # ig longer size2 = len(nums2) if size1 < size2: return self.findMedianSortedArrays(nums2,nums1) m1 = self.getMedian(nums1) m2 = self.getMedian(nums2) if size2 == 0: return m1[0] if size2 == 1: if size1 == 1: return (m1[0] + m2[0])/2 if size1 % 2 == 0: if nums2[0] < nums1[size1//2 - 1]: return nums1[size1//2 -1] if nums2[0] > nums1[size1//2]: return nums1[size1//2] else: return nums2[0] else: if nums2[0] < nums1[size1//2 - 1]: return (nums1[size1//2 - 1] + nums1[size1//2])/2 if nums2[0] > nums1[size1//2 + 1]: return (nums1[size1//2 + 1] + nums1[size1//2])/2 else: return (nums2[0] + nums1[size1//2])/2 if size1 % 2 == 0: if size2 % 2 == 0: if nums1[size1//2 - 1] > nums2[size2//2 - 1] and nums2[size2//2] > nums1[size1//2]: return m1[0] if nums1[size1//2 - 1] < nums2[size2//2 - 1] and nums2[size2//2] < nums1[size1//2]: return m2[0] if m1[0] < m2[0]: return self.findMedianSortedArrays(nums1[m2[1]:],nums2[:size2 - m2[1]]) if m1[0] > m2[0]: return self.findMedianSortedArrays(nums1[:size1 - m2[1]],nums2[m2[1]:]) else: return m1[0]
到此,關(guān)于“Java怎么尋找兩個(gè)有序數(shù)組的中位數(shù)”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。