- 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
- 🌲 每天打卡一道算法題，既是一個學習過程，又是一個分享的過程😜
- 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
- 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為算法大神吧🧐！
- 🌲 今天是力扣算法題持續打卡第4天🎈！
- 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
給定兩個大小分別為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并返回這兩個正序數組的 中位數 。
示例 1：
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數組 = [1,2,3] ，中位數 2
示例 2：
輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5
示例 3：
輸入：nums1 = [0,0], nums2 = [0,0]
輸出：0.00000
示例 4：
輸入：nums1 = [], nums2 = [1]
輸出：1.00000
示例 5：
輸入：nums1 = [2], nums2 = []
輸出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
解題思路
new 一個 List , 并將 nums1 和 nums2 都添加到list 中，然后進行排序。對于排序后的 list, 根據長度計算出中位數的index，進而計算出最終結果。
假設合并后的list長度為13，則從小到大第7個數字為中位數，resultIndex=6;
假設合并后的list長度為14，則從小到大第7，8個數字的平均值為中位數，index 分別為 6，7，此時resultIndex =7,resultIndex-1 =6 , 結果為 ( list[resultIndex-1] + list[resultIndex] ) / 2.0 ;
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
int m = nums1.Length;
int n = nums2.Length;
int len = m + n;
var resultIndex = len / 2;
List<int> list = new List<int>(nums1);
list.AddRange(nums2);
list.Sort();
if (len % 2 == 0)
{
return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
}
else
{
return list[resultIndex];
}
}
}
執行結果
執行通過，執行用時108ms，內存消耗28 MB.
復雜度分析
時間復雜度：O( (m+n)(1+log(m+n) ))
將長度為m,n的兩個數組添加到list，復雜度分別為常數級的m和n ；list.Sort()的復雜度根據官方文檔可得為 (m+n)log(m+n)，所以該方法時間復雜度為 O( m+n+(m+n)log(m+n) ) = O( (m+n)(1+log(m+n) ))
空間復雜度：O(m+n)
使用list的長度為m+n.
方法一使用了list.Sort() 方法，可以對list進行排序，但是，若題目給出的nums1 和 nums2 是無序數組，使用 list.Sort() 才算是 物有所用。 本題中 nums1 和 nums2 是有序數組，所以使用 list.Sort() 有寫 殺雞用宰牛刀的感覺，換句話說，這里面存在著效率的浪費。我們可以利用 【nums1 和 nums2 是有序數組】 這個條件，來精簡我們的排序。
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
// nums1 與 nums2 有序添加到list中
List<int> list = new List<int>();
int i = 0, j = 0;
int m = nums1.Length;
int n = nums2.Length;
int len = m + n;
var resultIndex = len / 2;
while (i < m && j < n)
{
if (nums1[i] < nums2[j])
list.Add(nums1[i++]);
else
list.Add(nums2[j++]);
}
while (i < m) list.Add(nums1[i++]);
while (j < n) list.Add(nums2[j++]);
if (len % 2 == 0)
{
return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
}
else
{
return list[resultIndex];
}
}
}
執行結果
執行結果 通過，執行用時 112ms，內存消耗 28.1MB
復雜度分析
時間復雜度：O(m+n)
i 和 j 一起把長度為 m 和 n 的兩個數組遍歷了一遍，所以時間復雜度為 O(m+n)
空間復雜度：O(m+n)
使用list的長度為m+n.
解題思路
給定兩個有序數組，要求找到兩個有序數組的中位數，最直觀的思路有以下兩種：
使用歸并的方式，合并兩個有序數組，得到一個大的有序數組。大的有序數組的中間位置的元素，即為中位數。
不需要合并兩個有序數組，只要找到中位數的位置即可。由于兩個數組的長度已知，因此中位數對應的兩個數組的下標之和也是已知的。維護兩個指針，初始時分別指向兩個數組的下標 00 的位置，每次將指向較小值的指針后移一位（如果一個指針已經到達數組末尾，則只需要移動另一個數組的指針），直到到達中位數的位置。
假設兩個有序數組的長度分別為 mm 和 nn，上述兩種思路的復雜度如何？
第一種思路的時間復雜度是 O(m+n)O(m+n)，空間復雜度是 O(m+n)O(m+n)。第二種思路雖然可以將空間復雜度降到 O(1)O(1)，但是時間復雜度仍是 O(m+n)O(m+n)。
如何把時間復雜度降低到 O(\log(m+n))O(log(m+n)) 呢？如果對時間復雜度的要求有 \loglog，通常都需要用到二分查找，這道題也可以通過二分查找實現。
根據中位數的定義，當 m+nm+n 是奇數時，中位數是兩個有序數組中的第 (m+n)/2(m+n)/2 個元素，當 m+nm+n 是偶數時，中位數是兩個有序數組中的第 (m+n)/2(m+n)/2 個元素和第 (m+n)/2+1(m+n)/2+1 個元素的平均值。因此，這道題可以轉化成尋找兩個有序數組中的第 kk 小的數，其中 kk 為 (m+n)/2(m+n)/2 或 (m+n)/2+1(m+n)/2+1。
假設兩個有序數組分別是 \text{A}A 和 \text{B}B。要找到第 kk 個元素，我們可以比較 \text{A}[k/2-1]A[k/2?1] 和 \text{B}[k/2-1]B[k/2?1]，其中 // 表示整數除法。由于 \text{A}[k/2-1]A[k/2?1] 和 \text{B}[k/2-1]B[k/2?1] 的前面分別有 \text{A}[0,…,k/2-2]A[0…k/2?2] 和 \text{B}[0,…,k/2-2]B[0…k/2?2]，即 k/2-1k/2?1 個元素，對于 \text{A}[k/2-1]A[k/2?1] 和 \text{B}[k/2-1]B[k/2?1] 中的較小值，最多只會有 (k/2-1)+(k/2-1) \leq k-2(k/2?1)+(k/2?1)≤k?2 個元素比它小，那么它就不能是第 kk 小的數了。
因此我們可以歸納出三種情況：
如果 \text{A}[k/2-1] < \text{B}[k/2-1]A[k/2?1]<B[k/2?1]，則比 \text{A}[k/2-1]A[k/2?1] 小的數最多只有 \text{A}A 的前 k/2-1k/2?1 個數和 \text{B}B 的前 k/2-1k/2?1 個數，即比 \text{A}[k/2-1]A[k/2?1] 小的數最多只有 k-2k?2 個，因此 \text{A}[k/2-1]A[k/2?1] 不可能是第 kk 個數，\text{A}[0]A[0] 到 \text{A}[k/2-1]A[k/2?1] 也都不可能是第 kk 個數，可以全部排除。
如果 \text{A}[k/2-1] > \text{B}[k/2-1]A[k/2?1]>B[k/2?1]，則可以排除 \text{B}[0]B[0] 到 \text{B}[k/2-1]B[k/2?1]。
如果 \text{A}[k/2-1] = \text{B}[k/2-1]A[k/2?1]=B[k/2?1]，則可以歸入第一種情況處理。
可以看到，比較 \text{A}[k/2-1]A[k/2?1] 和 \text{B}[k/2-1]B[k/2?1] 之后，可以排除 k/2k/2 個不可能是第 kk 小的數，查找范圍縮小了一半。同時，我們將在排除后的新數組上繼續進行二分查找，并且根據我們排除數的個數，減少 kk 的值，這是因為我們排除的數都不大于第 kk 小的數。
有以下三種情況需要特殊處理：
如果 \text{A}[k/2-1]A[k/2?1] 或者 \text{B}[k/2-1]B[k/2?1] 越界，那么我們可以選取對應數組中的最后一個元素。在這種情況下，我們必須根據排除數的個數減少 kk 的值，而不能直接將 kk 減去 k/2k/2。
如果一個數組為空，說明該數組中的所有元素都被排除，我們可以直接返回另一個數組中第 kk 小的元素。
如果 k=1k=1，我們只要返回兩個數組首元素的最小值即可。
用一個例子說明上述算法。假設兩個有序數組如下：
A: 1 3 4 9
B: 1 2 3 4 5 6 7 8 9
兩個有序數組的長度分別是 44 和 99，長度之和是 1313，中位數是兩個有序數組中的第 77 個元素，因此需要找到第 k=7k=7 個元素。
比較兩個有序數組中下標為 k/2-1=2k/2?1=2 的數，即 \text{A}[2]A[2] 和 \text{B}[2]B[2]，如下面所示：
A: 1 3 4 9
↑
B: 1 2 3 4 5 6 7 8 9
↑
由于 \text{A}[2] > \text{B}[2]A[2]>B[2]，因此排除 \text{B}[0]B[0] 到 \text{B}[2]B[2]，即數組 \text{B}B 的下標偏移（offset）變為 33，同時更新 kk 的值：k=k-k/2=4k=k?k/2=4。
下一步尋找，比較兩個有序數組中下標為 k/2-1=1k/2?1=1 的數，即 \text{A}[1]A[1] 和 \text{B}[4]B[4]，如下面所示，其中方括號部分表示已經被排除的數。
A: 1 3 4 9
↑
B: [1 2 3] 4 5 6 7 8 9
↑
由于 \text{A}[1] < \text{B}[4]A[1]<B[4]，因此排除 \text{A}[0]A[0] 到 \text{A}[1]A[1]，即數組 \text{A}A 的下標偏移變為 22，同時更新 kk 的值：k=k-k/2=2k=k?k/2=2。
下一步尋找，比較兩個有序數組中下標為 k/2-1=0k/2?1=0 的數，即比較 \text{A}[2]A[2] 和 \text{B}[3]B[3]，如下面所示，其中方括號部分表示已經被排除的數。
A: [1 3] 4 9
↑
B: [1 2 3] 4 5 6 7 8 9
↑
由于 \text{A}[2]=\text{B}[3]A[2]=B[3]，根據之前的規則，排除 \text{A}A 中的元素，因此排除 \text{A}[2]A[2]，即數組 \text{A}A 的下標偏移變為 33，同時更新 kk 的值： k=k-k/2=1k=k?k/2=1。
由于 kk 的值變成 11，因此比較兩個有序數組中的未排除下標范圍內的第一個數，其中較小的數即為第 kk 個數，由于 \text{A}[3] > \text{B}[3]A[3]>B[3]，因此第 kk 個數是 \text{B}[3]=4B[3]=4。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) {
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}
public int getKthElement(int[] nums1, int[] nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較
* 這里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個
* 取 pivot = min(pivot1, pivot2)，兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
* 這樣 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums1 數組
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums2 數組
* 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，減去刪除的數的個數
*/
int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
int kthElement = 0;
while (true) {
// 邊界情況
if (index1 == length1) {
return nums2[index2 + k - 1];
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
// 正常情況
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
}
鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
執行結果
執行結果 通過，執行用時 2ms，內存消耗 39.9MB
復雜度分析
時間復雜度：O(\log(m+n))O(log(m+n))
空間復雜度：O(1)
上邊的兩種思路，時間復雜度都達不到題目的要求 O(log(m+n)O(log(m+n)。看到 log，很明顯，我們只有用到二分的方法才能達到。我們不妨用另一種思路，題目是求中位數，其實就是求第 k 小數的一種特殊情況，而求第 k 小數有一種算法。
解法二中，我們一次遍歷就相當于去掉不可能是中位數的一個值，也就是一個一個排除。由于數列是有序的，其實我們完全可以一半兒一半兒的排除。假設我們要找第 k 小數，我們可以每次循環排除掉 k/2 個數。看下邊一個例子。
假設我們要找第 7 小的數字。
我們比較兩個數組的第 k/2 個數字，如果 k 是奇數，向下取整。也就是比較第 33 個數字，上邊數組中的 44 和下邊數組中的 33，如果哪個小，就表明該數組的前 k/2 個數字都不是第 k 小數字，所以可以排除。也就是 11，22，33 這三個數字不可能是第 77 小的數字，我們可以把它排除掉。將 13491349 和 4567891045678910 兩個數組作為新的數組進行比較。
更一般的情況 A[1] ，A[2] ，A[3]，A[k/2] … ，B[1]，B[2]，B[3]，B[k/2] … ，如果 A[k/2]<B[k/2] ，那么A[1]，A[2]，A[3]，A[k/2]都不可能是第 k 小的數字。
A 數組中比 A[k/2] 小的數有 k/2-1 個，B 數組中，B[k/2] 比 A[k/2] 小，假設 B[k/2] 前邊的數字都比 A[k/2] 小，也只有 k/2-1 個，所以比 A[k/2] 小的數字最多有 k/1-1+k/2-1=k-2個，所以 A[k/2] 最多是第 k-1 小的數。而比 A[k/2] 小的數更不可能是第 k 小的數了，所以可以把它們排除。
橙色的部分表示已經去掉的數字。
由于我們已經排除掉了 3 個數字，就是這 3 個數字一定在最前邊，所以在兩個新數組中，我們只需要找第 7 - 3 = 4 小的數字就可以了，也就是 k = 4。此時兩個數組，比較第 2 個數字，3 < 5，所以我們可以把小的那個數組中的 1 ，3 排除掉了。
我們又排除掉 2 個數字，所以現在找第 4 - 2 = 2 小的數字就可以了。此時比較兩個數組中的第 k / 2 = 1 個數，4 == 4，怎么辦呢？由于兩個數相等，所以我們無論去掉哪個數組中的都行，因為去掉 1 個總會保留 1 個的，所以沒有影響。為了統一，我們就假設 4 > 4 吧，所以此時將下邊的 4 去掉。
由于又去掉 1 個數字，此時我們要找第 1 小的數字，所以只需判斷兩個數組中第一個數字哪個小就可以了，也就是 4。
所以第 7 小的數字是 4。
我們每次都是取 k/2 的數進行比較，有時候可能會遇到數組長度小于 k/2的時候。
此時 k / 2 等于 3，而上邊的數組長度是 2，我們此時將箭頭指向它的末尾就可以了。這樣的話，由于 2 < 3，所以就會導致上邊的數組 1，2 都被排除。造成下邊的情況。
由于 2 個元素被排除，所以此時 k = 5，又由于上邊的數組已經空了，我們只需要返回下邊的數組的第 5 個數字就可以了。
從上邊可以看到，無論是找第奇數個還是第偶數個數字，對我們的算法并沒有影響，而且在算法進行中，k 的值都有可能從奇數變為偶數，最終都會變為 1 或者由于一個數組空了，直接返回結果。
所以我們采用遞歸的思路，為了防止數組長度小于 k/2，所以每次比較 min(k/2，len(數組) 對應的數字，把小的那個對應的數組的數字排除，將兩個新數組進入遞歸，并且 k 要減去排除的數字的個數。遞歸出口就是當 k=1 或者其中一個數字長度是 0 了。
代碼
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//將偶數和奇數的情況合并，如果是奇數，會求兩次同樣的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//讓 len1 的長度小于 len2，這樣就能保證如果有數組空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
執行結果
執行結果 通過，執行用時 2ms，內存消耗 39.8MB
復雜度分析
時間復雜度： O(log(m+n）O(log(m+n）
空間復雜度：O(1)
