當(dāng)前位置：首頁(yè) > news >正文

sm.wordpress蘇州seo推廣

news 2025/7/2 15:14:19

sm.wordpress,蘇州seo推廣,網(wǎng)絡(luò)個(gè)性化定制,手機(jī)網(wǎng)址2021年免費(fèi)不封. - 力扣（LeetCode） 題目給定兩個(gè)大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的中位數(shù) 。算法的時(shí)間復(fù)雜度應(yīng)該為 O(log (mn)) 。示例 1： 輸入：nums1 …

. - 力扣（LeetCode）

題目

給定兩個(gè)大小分別為?m?和?n?的正序（從小到大）數(shù)組?nums1?和?nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的?中位數(shù)?。

算法的時(shí)間復(fù)雜度應(yīng)該為?O(log (m+n))?。

示例 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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
$-10^6 <= nums1[i], nums2[i] <= 10^6$

解題方案

首先明確中位數(shù)的位置

1. 暴力解法（合并數(shù)組）

合并成一個(gè)新數(shù)組，然后sort，取中位數(shù)。

邊界情況：合并后數(shù)組的長(zhǎng)度為0，則無(wú)中位數(shù)
合并數(shù)組(nums)長(zhǎng)度為偶數(shù)(n)，則中位數(shù)為第 $\frac{n}{2}$ 位和第 $\frac{n}{2}+1$ 位的平均值，即 $mid=\frac{nums[\frac{n}{2}-1]+nums[\frac{n}{2}]}{2}$
合并數(shù)組(nums)長(zhǎng)度為奇數(shù)(n)，則中位數(shù)為第 $\frac{n+1}{2}$ 位，即 $nums[\frac{n-1}{2}]$

接下來(lái)，人生苦短，我用Python~

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# 合并數(shù)組并排序nums1.extend(nums2)nums1.sort()length = len(nums1)if length < 1:return Noneif length % 2 == 0:return (nums1[length // 2 - 1] + nums1[length // 2]) / 2else:return nums1[length // 2]

分析時(shí)空復(fù)雜度

記nums1長(zhǎng)度為m, nums2長(zhǎng)度為n
合并數(shù)組時(shí)間復(fù)雜度是 $O(m+n)$ ，空間復(fù)雜度是 $O(m+n)$
數(shù)組排序時(shí)間復(fù)雜度是 $O((n+m)log(n+m))$ ，空間復(fù)雜度是 $O((n+m)log(n+m))$

故總的時(shí)間復(fù)雜度是 $O((n+m)log(n+m))$ ，空間復(fù)雜度是 $O((n+m)log(n+m))$

雖然看上去代碼非常精煉，但是從時(shí)空復(fù)雜度上看，算法并不好，畢竟題目中"正序（從小到大）數(shù)組"這個(gè)條件沒(méi)有用到。因此考慮有序歸并

2. 暴力解法優(yōu)化版（有序合并數(shù)組）

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:m = len(nums1)n = len(nums2)# 合并數(shù)組nums = []if m == 0:nums = nums2elif n == 0:nums = nums1else:index_1 = 0index_2 = 0while True:if index_1 >= m and index_2 >= n:breakelif index_2 >= n or (index_1 < m and nums1[index_1] <= nums2[index_2]):nums.append(nums1[index_1])index_1 += 1elif index_1 >=m or (index_2 < n and nums1[index_1] > nums2[index_2]):nums.append(nums2[index_2])index_2 += 1total_length = len(nums)if total_length < 1:return Noneelif total_length % 2 == 0:return (nums[total_length // 2 - 1] + nums[total_length // 2]) / 2else:return nums[total_length // 2]

分析時(shí)空復(fù)雜度

時(shí)間復(fù)雜度為合并數(shù)組花費(fèi)的時(shí)間， $O(m+n)$
空間復(fù)雜度為合并后數(shù)組的空間， $O(m+n)$ ?（如果不存儲(chǔ)合并的數(shù)組，空間復(fù)雜度可以做到O(1)）

題目給出的條件都用上了，時(shí)空復(fù)雜度也得到了提升，但仍然不符合題目要求的?O(log (m+n))的時(shí)間復(fù)雜度，需要進(jìn)一步優(yōu)化。

有序數(shù)組尋找中位數(shù)，考慮二分法。

`3. 二分法`

考慮一個(gè)長(zhǎng)度為n有序數(shù)組的中位數(shù)，其中位數(shù)：

如果n為奇數(shù)，則中位數(shù)為第 $\frac{n+1}{2}$ 大的數(shù)。
如果n為偶數(shù)，則中位數(shù)為第 $\frac{n}{2}$ 大的數(shù)和第 $\frac{n+1}{2}$ 大的數(shù)的平均值。

因此，中位數(shù)問(wèn)題可以轉(zhuǎn)換為另一個(gè)問(wèn)題，尋找數(shù)組中第k小的數(shù)

（對(duì)于長(zhǎng)度為偶數(shù)的情況，需要尋找兩次，并取平均值）

class Solution:def getKthNumber(self,  nums1: List[int], nums2: List[int], k: int) -> int:"""尋找兩個(gè)正序整數(shù)數(shù)組中，第k小的數(shù)"""passdef findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""中位數(shù)計(jì)算入口函數(shù)"""total_length = len(num1) + len(nums2)if total_length < 1:return Noneelif total_length % 2 == 0:return (self.getKthNumber(nums1, nums2, total_length // 2) + self.getKthNumber(nums1, nums2, total_length // 2 + 1)) / 2else:return self.getKthNumber(num1, nums2, total_length // 2 + 1)

接著看如何尋找兩個(gè)正序數(shù)組中第k小的數(shù)：

如果時(shí)間復(fù)雜度是O(log (m+n))，考慮用二分法。

先看下面這個(gè)例子：

由此，我們可以總結(jié)我們兩個(gè)正序數(shù)組中，尋找第k小的數(shù)的思路：

1. 如果k=1, 則首先比較兩個(gè)數(shù)組首位元素，取最小的一個(gè)。

2. 如果k>1, 則比較兩個(gè)數(shù)組中第 $\frac{k}{2}$ 個(gè)元素，較小的一個(gè)數(shù)組中的第1~ $\frac{k}{2}$ 個(gè)元素一定是小于我們目標(biāo)值的，因此可以排除這一段（如上圖中灰色部分），在剩余元素中繼續(xù)尋找第( $k-\frac{k}{2}$ )小的元素。

3. 如果某個(gè)數(shù)組完全被排除掉了，則直接在剩余的另一個(gè)數(shù)組中定位目標(biāo)元素即可。如下面的例子：

class Solution:def getKthNumber(self,  nums1: List[int], nums2: List[int], k: int) -> int:"""尋找兩個(gè)正序整數(shù)數(shù)組中，第k大的數(shù)"""# 記錄數(shù)組長(zhǎng)度m = len(nums1)n = len(nums2)# 記錄數(shù)組可以查找的起始位置索引index_1 = 0index_2 = 0while True:# 極端情況1 - nums1已經(jīng)被排除為空if index_1 >= m:return nums2[index_2 + k - 1]# 極端情況2 - nums2已經(jīng)被排除為空if index_2 >= n:return nums1[index_1 + k - 1]# 極端情況3 - 尋找最小的數(shù)if k == 1:return min(nums1[index_1], nums2[index_2])# 正常情況, 二分查找new_index_1 = min(k // 2 - 1 + index_1, m - 1)new_index_2 = min(k // 2 - 1 + index_2, n - 1)if nums1[new_index_1] <= nums2[new_index_2]:k -= (new_index_1 - index_1 + 1)index_1 = new_index_1 + 1else:k -= (new_index_2 - index_2 + 1)index_2 = new_index_2 + 1def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""尋找中位數(shù) 入口函數(shù)"""total_length = len(nums1) + len(nums2)if total_length < 1:return Noneelif total_length % 2 == 0:return (self.getKthNumber(nums1, nums2, total_length // 2) + self.getKthNumber(nums1, nums2, total_length // 2 + 1)) / 2else:return self.getKthNumber(nums1, nums2, total_length // 2 + 1)

分析時(shí)空復(fù)雜度

時(shí)間復(fù)雜度 $O(log(m+n))$
空間復(fù)雜度 $O(1)$ ?

AI會(huì)怎么做？

智譜清言給出了一種更高效的解法，劃分?jǐn)?shù)組二分法。

思路：

對(duì)一個(gè)長(zhǎng)度為n的數(shù)組，從任意位置i將數(shù)組劃分為兩部分，可以有n+1種分發(fā)（ $i \in [0, n]$ ），如圖所示，4個(gè)元素的數(shù)組，有4+1=5種劃分方法。

中位數(shù)的作用是什么呢？將一個(gè)集合劃分為兩個(gè)長(zhǎng)度相等的子集，其中一個(gè)子集中的元素總是大于另一個(gè)子集中的元素。
對(duì)數(shù)組A從i位置進(jìn)行劃分，對(duì)數(shù)組B在j位置劃分，數(shù)組A的左半部分和數(shù)組B的左半部分合起來(lái)叫做left_part, 數(shù)組A的有半部分和數(shù)組B的右半部分合起來(lái)叫做right_part，則中位數(shù)是這樣的一種劃分：
對(duì)于兩個(gè)數(shù)組長(zhǎng)度之和為偶數(shù)的情況： $\left\{\begin{matrix} {len(left\_part) == len(right\_part) }\\{max(left\_part) <= min(right\_part)} \end{matrix}\right.$ ，中位數(shù)為 $mid=\frac{max(left\_part)+min(right\_part)}{2}$ ,此時(shí)劃分位置滿足 $i + j = m-i+n-j\quad i\in[0,m],j\in[0,n]$
對(duì)于兩個(gè)數(shù)組長(zhǎng)度之和為奇數(shù)的情況： $\left\{\begin{matrix} {len(left\_part) == len(right\_part) + 1}\\{max(left\_part) <= min(right\_part)} \end{matrix}\right.$ ，中位數(shù)為 $mid = max(left\_part)$ ，此時(shí)劃分位置滿足 $i+j=m-i + n-j +1\quad i\in[0,m],j\in[0,n]$
合并上述兩種，可以知道中位數(shù)情況下的劃分： $i+j =int(\frac{m+n+1}{2}) \qquad i\in[0,m],j\in[0,n]$
如果我們保證 $m <=n$ (避免j計(jì)算出負(fù)數(shù))，可以導(dǎo)出： $j=int(\frac{m+n+1}{2}) - i \qquad j\in[0,n]$
通過(guò)上述推導(dǎo)，中位數(shù)問(wèn)題可以轉(zhuǎn)換為：尋找 $i\in[0,m]$ ，使得： $B[j-1] \leqslant A[i]$ 且 $A[i-1]\leqslant B[j]$ ，其中 $j=int(\frac{m+n+1}{2}) - i$ ，
進(jìn)一步簡(jiǎn)化為：在 $[0,m]$ 中尋找最大的 $i$ ，使得 $A[i-1]\leqslant B[j]$ ,其中 $j=int(\frac{m+n+1}{2}) - i$ 。接下來(lái)就可以在 $[0,m]$ 上對(duì) $i$ 進(jìn)行二分查找了。

如此復(fù)雜的推導(dǎo)過(guò)程，又是擔(dān)心被AI取代的一天。。。

def findMedianSortedArrays(nums1, nums2):# 確保 nums1 是較短的數(shù)組if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m, n = len(nums1), len(nums2)imin, imax, half_len = 0, m, (m + n + 1) // 2while imin <= imax:i = (imin + imax) // 2j = half_len - iif i < m and nums1[i] < nums2[j - 1]:# i 需要增大imin = i + 1elif i > 0 and nums1[i - 1] > nums2[j]:# i 需要減小imax = i - 1else:# 找到合適的 i 和 jmax_of_left = 0if i == 0: max_of_left = nums2[j - 1]elif j == 0: max_of_left = nums1[i - 1]else: max_of_left = max(nums1[i - 1], nums2[j - 1])if (m + n) % 2 == 1:return max_of_leftmin_of_right = 0if i == m: min_of_right = nums2[j]elif j == n: min_of_right = nums1[i]else: min_of_right = min(nums1[i], nums2[j])return (max_of_left + min_of_right) / 2.0# 示例
print(findMedianSortedArrays([1, 3], [2]))  # 輸出: 2.0
print(findMedianSortedArrays([1, 2], [3, 4]))  # 輸出: 2.5

查看全文

http://aloenet.com.cn/news/29320.html

国产亚洲精品福利在线无卡一,国产精久久一区二区三区,亚洲精品无码国模,精品久久久久久无码专区不卡

sm.wordpress蘇州seo推廣

題目

解題方案

1. 暴力解法（合并數(shù)組）

分析時(shí)空復(fù)雜度

2. 暴力解法優(yōu)化版（有序合并數(shù)組）

分析時(shí)空復(fù)雜度

`3. 二分法`

分析時(shí)空復(fù)雜度

AI會(huì)怎么做？

相關(guān)文章：