題目描述

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

解答思路

我的想法是先歸并排序再直接返回下標中位數
代碼

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {int i=0,j=0,k=0;int c[nums1Size+nums2Size];while(i<nums1Size&&j<nums2Size){if(nums1[i]<nums2[j])c[k++]=nums1[i++];elsec[k++]=nums2[j++];}while(i<nums1Size)c[k++]=nums1[i++];while(j<nums2Size)c[k++]=nums2[j++];if((nums1Size+nums2Size)%2==1)return c[(nums1Size+nums2Size)/2];elsereturn (c[(nums1Size+nums2Size)/2-1]+c[(nums1Size+nums2Size)/2])/2.0;
}

結果

復雜度分析
時間復雜度：O(m+n）
空間復雜度:O(n+m)

解法二，二分查找法(最優解)

二分查找的算法模板from算法模板

bool check(int x){ /* ... */}//檢查x是否滿足某種性質//區間[l,r]被劃分成[l,mid] 和 [mid+1,r]時使用；
int bsearch_1(int l,int r)
{while(l<r){int mid = l+r >>1;if(check(mid)) r=mid;else l = mid + 1;}return l;
}
//區間[l,r]被劃分成[l,mid-1] 和 [mid,r]時使用：
int bsearch_2(int l,int r)
{while(l<r){int mid = l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}return l;
}

既然題目要求對數級別的時間復雜度，我們必須考慮使用二分查找。這里的難點在于，我們不是在一個簡單的數組上進行二分，而是在一個“虛擬”的合并數組上進行。

核心思想：轉化問題
尋找中位數，本質上是在尋找一個“分割點”，這個分割點能將一個集合分成左右兩個部分，且左邊部分的所有元素都小于等于右邊部分的所有元素。

對于這道題，我們要在 nums1 和 nums2 中找到兩個分割點，將兩個數組都分成左右兩部分。這兩個分割點需要滿足以下兩個條件：
長度條件：左半部分所有元素的個數之和 等于 右半部分所有元素的個數之和（或多一個，當總數為奇數時）。
大小條件：左半部分所有元素的最大值 小于等于 右半部分所有元素的最小值。
只要我們找到了滿足這兩個條件的分割點，中位數就自然而然地由分割點周圍的元素決定了

具體步驟：
為了簡化，我們假設 nums1 是長度較短的那個數組（如果不是，可以交換它們）。

• 我們對較短的數組 nums1 進行二分查找。我們要查找的不是一個值，而是一個合適的分割線索引 i。這個 i 將 nums1 分成 nums1[0…i-1]（左半部分）和 nums1[i…m-1]（右半部分）。

• 設總長度的一半為 halfLen = (m + n + 1) / 2。（這里 +1 是一個小技巧，可以同時處理奇偶情況）。

• 一旦 nums1 的分割線 i 確定了，nums2 的分割線 j 也隨之確定，必須滿足 i + j = halfLen，所以 j = halfLen - i。j 將 nums2 分成 nums2[0…j-1] 和 nums2[j…n-1]。

• 現在我們有了四個關鍵的邊界值：
  nums1 左半部分的最大值：nums1[i-1] (設為 L1)
  nums1 右半部分的最小值：nums1[i] (設為 R1)
  nums2 左半部分的最大值：nums2[j-1] (設為 L2)
  nums2 右半部分的最小值：nums2[j] (設為 R2)

• 接下來，我們檢查“大小條件”是否滿足。正確的分割線必須滿足：L1 <= R2 并且 L2 <= R1。
  如果 L1 > R2：說明 nums1 的分割線 i 太靠右了，nums1 左邊的數太大了。我們需要將 i 向左移動。在二分查找中，這意味著要縮小查找區間的右邊界 (high = i - 1)。
  如果 L2 > R1：說明 nums1 的分割線 i 太靠左了，nums1 右邊的數太小了（等價于 nums2 左邊的數太大了）。我們需要將 i 向右移動。在二分查找中，這意味著要擴大查找區間的左邊界 (low = i + 1)。
  如果同時滿足 L1 <= R2 和 L2 <= R1：恭喜，我們找到了完美的分割線！現在可以計算中位數了：
  如果總長度 (m+n) 是奇數：中位數就是兩個左半部分中的最大值，即 max(L1, L2)。
  如果總長度 (m+n) 是偶數：中位數是左半部分最大值和右半部分最小值的平均值，即 (max(L1, L2) + min(R1, R2)) / 2.0。

• 處理邊界：當 i 或 j 為 0 或數組長度時，其左邊或右邊可能沒有元素。這時我們可以把 L1, L2 視為負無窮大，把 R1, R2 視為正無窮大，這樣大小比較的邏輯依然成立。

代碼實現：
不太會寫，學習一下g老師的代碼

#include <stdio.h>
#include <limits.h> // 用于 INT_MIN 和 INT_MAX// 一個簡單的宏來獲取最大值和最小值，比引入 math.h 更輕量
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {// 確保 nums1 是較短的數組，這樣可以減少二分查找的次數if (nums1Size > nums2Size) {return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);}int m = nums1Size;int n = nums2Size;int low = 0, high = m;// 在較短的數組 nums1 上進行二分查找while (low <= high) {// partition1 是 nums1 的分割點int partition1 = low + (high - low) / 2;// partition2 是 nums2 的分割點，根據總長度的一半來計算int partition2 = (m + n + 1) / 2 - partition1;// 獲取分割線左側的最大值// 如果 partition1 為 0，說明 nums1 的左半部分為空，取負無窮int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];// 如果 partition2 為 0，說明 nums2 的左半部分為空，取負無窮int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];// 獲取分割線右側的最小值// 如果 partition1 等于 m，說明 nums1 的右半部分為空，取正無窮int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];// 如果 partition2 等于 n，說明 nums2 的右半部分為空，取正無窮int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];// 檢查是否找到了完美的分割線if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {// 如果總元素個數是偶數if ((m + n) % 2 == 0) {return (MAX(maxLeft1, maxLeft2) + MIN(minRight1, minRight2)) / 2.0;} else { // 如果總元素個數是奇數return (double)MAX(maxLeft1, maxLeft2);}} // 如果 nums1 左邊的最大值大于了 nums2 右邊的最小值// 說明 partition1 太大了，需要向左移動else if (maxLeft1 > minRight2) {high = partition1 - 1;} // 否則說明 partition1 太小了，需要向右移動else {low = partition1 + 1;}}// 如果程序運行到這里，說明輸入數組不是有序的，按題目要求不會發生// 在實際工程中，這里應該拋出異常return -1.0; 
}// ------ 主函數用于測試 ------
int main() {// 測試用例 1: 奇數總長int nums1[] = {1, 3};int nums2[] = {2};double median1 = findMedianSortedArrays(nums1, 2, nums2, 1);printf("Test Case 1: Median is %f\n", median1); // 應該輸出 2.0// 測試用例 2: 偶數總長int nums3[] = {1, 2};int nums4[] = {3, 4};double median2 = findMedianSortedArrays(nums3, 2, nums4, 2);printf("Test Case 2: Median is %f\n", median2); // 應該輸出 2.5return 0;
}

運行結果：

復雜度分析：
時間復雜度：O(log(min(m,n)))
空間復雜度：O(1)
ok see you next time~