題目

題目：給定兩個大小分別為 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

進階：你能設計一個時間復雜度為 O(log (m+n)) 的演算法解決此問題嗎？

題目分析

1. 我們要從兩個已經排好序的陣列里面找出他們的中位數，首先想到就是把兩個陣列合并到一個有序陣列里面，這樣我們就可以很容易找出中位數
2. 同時也要考慮元素個數是奇數還是偶數，這樣以便于我們判斷中位數是直接是陣列里面的元素，或者需要我們計算，
3. 對于兩個已經排好序的陣列進行合并可以參照歸并排序法

常規解法

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int i=0,j=0,k=0;
    int* arr=(int*)malloc((nums1Size+nums2Size)*sizeof(int));   //(1)
    while(i<nums1Size&&j<nums2Size){
        arr[k++]=nums1[i]>nums2[j]?nums2[j++]:nums1[i++];
    }
    while(i<nums1Size){
        arr[k++]=nums1[i++];
    }
    while(j<nums2Size){
        arr[k++]=nums2[j++];
    }                                                          //(2)
    int temp=nums1Size+nums2Size;
    if(temp%2!=0){ 
        return arr[temp/2];                                   //(3)
    }
    else{
        return (arr[temp/2]+arr[temp/2-1])*1.0/2;            //(4)
    }
}

(1) 開辟一個陣列空間用來存放兩個合并后的陣列，C語言不支持使用
int nums[nums1Size+nums2Size]來開辟陣列
(2)這里是歸并排序
(3)如果是奇數直接是我們需要的
(4)如果是偶數，需要計算，不能忘記那個1.0

我們可以看見，在速度上很快 ，但是卻很消耗記憶體
經過多次測驗，發現這是一次特殊的，不知道為什么跑這么快

但是事實上我們不需要創建一個新陣列，只需要維護兩個指標找到陣列下標就可以實作，其思想還是來源解法1

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int len = nums1Size + nums2Size;
	int p1 = 0, p2 = 0;
	int left = 0, right = 0;
	int i = 0;
	for (i = 0; i <= len / 2; ++i) {
		left = right;
		if (p1 < nums1Size && (p2 >= nums2Size || nums1[p1] < nums2[p2])) {
			right = nums1[p1++];
		}                                 //(1)
		else
			right = nums2[p2++];
	}
	if (len % 2 == 0)
		return (left + right)*1.0 / 2;
	else
		return right;
}

1. 我們需要兩個數來標記我們需要的數，其中left表示前一個,right表示當前最小的一個
2. （1）選取最小的在陣列nums1的條件是，nums1中還有元素，nums2中沒有元素，nums中當前元素大于nums1中當前元素，經過條件判斷寫成代碼形式

PS：做到后面感覺不對勁
經過多次測驗

時間波動比較大

進階解法

我們看到提示中有一個進階解法，出現log一般都要考慮二分法
這個進階解法比較復雜，建議點擊鏈接去官網看此解法
不過官網沒有給出C的代碼，下面我根據決議寫出C的代碼以供參考，

int getKthNum(int* nums1, int nums1Size, int* nums2, int nums2Size,int k) {
	int p1 = 0, p2 = 0;
	int KthNum = 0;
	while (1) {
		if (p1 == nums1Size)
			return nums2[p2 + k - 1];
		if (p2 == nums2Size)
			return nums1[p1 + k - 1];
		if (k == 1)
			return nums1[p1] > nums2[p2] ? nums2[p2] : nums1[p1];
		int mid = k / 2;
		int newP1 = (p1 + mid> nums1Size?nums1Size:p1+mid) - 1;
		int newP2 = (p2 + mid>nums2Size?nums2Size:p2+mid) - 1;
		int pivot1 = nums1[newP1], pivot2 = nums2[newP2];
		if (pivot1 <= pivot2) {
			k -= (newP1 - p1 + 1);
			p1 = newP1 + 1;
		}
		else {
			k -= (newP2 -p2 + 1);
			p2 = newP2 + 1;
		}
	}

}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int len = nums1Size + nums2Size;
	if (len % 2 == 1) {
		int mid = len / 2;
		double median = getKthNum(nums1, nums1Size,nums2, nums2Size, mid+ 1);
		return median;
	}
	else {
		int mid1 = len / 2 - 1, mid2 = len / 2;
		double median = (getKthNum(nums1, nums1Size, nums2, nums2Size, mid1 + 1) + getKthNum(nums1, nums1Size, nums2, nums2Size, mid2 + 1)) / 2.0;
		return median;
	}
}

可以看見這個速度和記憶體消耗都要比前面兩種解法要小，