摘要:解法解法應(yīng)該是最常見的一種解法,就是將兩個數(shù)組頭尾相加合并起來,然后重新排序,例如輸入兩個數(shù)組,合并之后變?yōu)椋缓笄蟪鲋形粩?shù)。如果兩個數(shù)組長度和為偶數(shù),那么中位數(shù)有兩個,否則只有一個
題目
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)).
You may assume nums1 and nums2 cannot be both empty.
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
解析給出兩個已經(jīng)排序好的數(shù)組,求出兩個數(shù)組合起來的中位數(shù)。
題目意思很清晰,條件和結(jié)果都很簡單,條件是兩個已經(jīng)排序好的數(shù)組,結(jié)果需要兩個數(shù)組合起來之后取中位數(shù)。
解法1應(yīng)該是最常見的一種解法,就是將兩個數(shù)組頭尾相加合并起來,然后重新排序,例如輸入 [1,2] [3,4] 兩個數(shù)組,合并之后變?yōu)閇1,2,3,4],然后求出中位數(shù)。
這種解法很簡潔,但是在內(nèi)存和性能方面的表現(xiàn)非常的差,因為兩個已經(jīng)排列好的數(shù)組頭尾相加合并之后會變成一個無序的數(shù)組,同時占用內(nèi)存增加了一倍。
效率更高點的解法應(yīng)該是利用好兩個數(shù)組已經(jīng)排序好的這個特性,通過游標(biāo)記錄移動路徑,并記錄移動的次數(shù),當(dāng)移動的次數(shù)達(dá)到兩個數(shù)組的中位數(shù)時,取得游標(biāo)附近的值,求得中位數(shù)。
public double findMedianSortedArrays(int[] nums1, int[] nums2) { int num1Size = nums1.length , num2Size = nums2.length; double result = 0.0; int size = num1Size + num2Size; int index = 0; int num1Index = 0 , num2Index = 0; int[] medianArray = new int[2]; int currentValue = 0; while(index <= size/2){ if(num1Index >= num1Size){ currentValue = nums2[num2Index++]; }else if(num2Index >= num2Size){ currentValue = nums1[num1Index++]; } else if(nums1[num1Index] > nums2[num2Index]){ currentValue = nums2[num2Index++]; } else{ currentValue = nums1[num1Index++]; } medianArray[0] = medianArray[1]; medianArray[1] = currentValue; index++; } // 如果兩個數(shù)組長度和為偶數(shù),那么中位數(shù)有兩個,否則只有一個 if(size%2==0){ result = (medianArray[0] + medianArray[1]) / 2.0; }else{ result = medianArray[1]; } return result; }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/72419.html
摘要:復(fù)雜度思路因為要找中位數(shù),又是在兩個的數(shù)組里面。所以考慮用二分法。二分法經(jīng)常適合的接下來考慮如何二分。然后對和進(jìn)行比較,記為和。所以為了縮小搜索范圍,我們可以扔掉這些數(shù),在的剩下來的數(shù)中和的數(shù)組中接著找。說明中沒有個數(shù)可以尋找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...
摘要:難度為這個題目描述很清晰給出兩個排序好的數(shù)組求這兩個數(shù)組的中位數(shù)在解這個題的過程中會碰到以下的問題先合起來重新排序是不可行的時間復(fù)雜度太高為先歸并排序也是不可行的時間復(fù)雜度為用類似桶排的方法時間復(fù)雜度為不可行可能會碰到多種全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...
摘要:自第一篇收集向的文章發(fā)布后,近年半沒更新這個專欄了。今天是分類中第一個的,叫做。不過這樣需要兩個數(shù)組各掃一遍,然而我們的目的只是要取到中間值,似乎并不用完整的掃一遍。那么也就意味著,我們最終要記錄的值可能是兩個。 大家好,我叫張小豬。 自第一篇收集向的文章發(fā)布后,近 1 年半沒更新這個專欄了。最近面試中發(fā)現(xiàn)將近 60% 的候選人對于 bubble sort 面露難色,于是心悸于自己也忘...
摘要:由于要求的時間,所以選擇二分法。思路是找到兩個數(shù)組合并起來的第個元素。這樣只需計算兩個數(shù)組的中位數(shù)是第幾個元素,代入功能函數(shù)即可。據(jù)此,根據(jù)二分法的性質(zhì),我們在遞歸時可以將前即個元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...
摘要:最新解法及思路有兩個有序數(shù)組和,他們的大小各是和,請找出這兩個數(shù)組所有數(shù)的中位數(shù),總得時間復(fù)雜度不超過歸并計數(shù)法復(fù)雜度時間空間思路如果對時間復(fù)雜度沒有要求,這個方法是實現(xiàn)起來最簡單的,我們只需要從下往上依次數(shù)個元素即可。 Median of Two Sorted Arrays 最新解法及思路:https://yanjia.li/zh/2018/11/... There are two...
閱讀 933·2023-04-26 01:34
閱讀 3368·2023-04-25 20:58
閱讀 3310·2021-11-08 13:22
閱讀 2121·2019-08-30 14:17
閱讀 2533·2019-08-29 15:27
閱讀 2683·2019-08-29 12:45
閱讀 3007·2019-08-29 12:26
閱讀 2821·2019-08-28 17:51