[LeetCode] 4. Median of Two Sorted Arrays

轉自LeetCode

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)).

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

<Solution>

這題要從兩個 sorted array 找到中位數，時間要求 O(log(m+n))

看到時間要求，就知道不能合併完 array 再找

解題的想法是，在合併的過程中，找到中位數就結束

因為中位數的位置可以從兩個 array 的長度先知道，要注意的是長度奇偶問題

想法如下

• 先求出中位數的位置，並判斷合併後的長度是奇數還是偶數
• 開始合併，每次從兩個 array 中抓比較小的那個出來
• 因為要處理長度是奇數偶數的問題，所以保留兩個值(目前和上一個)
• 當到達中位數的位置，結束迴圈，並根據長度是奇數偶數算出中位數

	class Solution {
	public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	int totalLen = nums1.size() + nums2.size();
	bool isEven = ((totalLen % 2) == 0) ? true : false;
	int median = totalLen / 2; //> ans is here
	int medianIdx = -1, index_1 = 0, index_2 = 0;
	double curNum = 0.0, prvNum = 0.0;
	while(index_1 < nums1.size() || index_2 < nums2.size()) {
	if(index_1 < nums1.size() && index_2 < nums2.size()) { //> both arrays are not empty
	if(nums1[index_1] < nums2[index_2]) {
	prvNum = curNum;
	curNum = static_cast<double>(nums1[index_1++]);
	}
	else {
	prvNum = curNum;
	curNum = static_cast<double>(nums2[index_2++]);
	}
	}
	else if(index_1 == nums1.size() && index_2 < nums2.size()) { //> array1 is empty
	prvNum = curNum;
	curNum = static_cast<double>(nums2[index_2++]);
	}
	else { //> array2 is empty
	prvNum = curNum;
	curNum = static_cast<double>(nums1[index_1++]);
	}
	//> has one more element
	++medianIdx;
	//> reach the position of median
	if(medianIdx == median) {
	break;
	}
	}
	return (isEven == true) ? (curNum + prvNum) / 2.0 : curNum;
	}
	};

view raw findmediam.cpp hosted with ❤ by GitHub

最後有看到一個神解法，速度會快很多

但是不是很懂他的邏輯，需要再研究