---
tags: leetcode,解題報告,
---
# 4. Median of Two Sorted Arrays
題目連結: [LeetCode](https://leetcode.com/problems/median-of-two-sorted-arrays/)

## 題目說明
輸入兩個已排序好的Vector,找出兩Vector資料的中位數
兩`Vector`的長度分別為 $m, n$

## 想法

1. 合併`Vector`的同時進行排序
2. 計算中位數

## 參考解法
:::spoiler 點我查看
Runtime: 45ms
Memory: 90.3 MB
時間複雜度: 應該是 $O(m+n)$
空間複雜度: 應該是 $O(m+n)$

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int v1_size = nums1.size(),
            v2_size = nums2.size();
        vector<int> merged_array;
        int i=0, j=0;
        while (i<v1_size and j<v2_size){
            if (nums1[i] < nums2[j]){
                merged_array.push_back(nums1[i++]);
            }
            else{
                merged_array.push_back(nums2[j++]);
            }
        }
        while (i<v1_size){
            merged_array.push_back(nums1[i++]);
        }
        while (j<v2_size){
            merged_array.push_back(nums2[j++]);
        }

        cout<<fixed<<setprecision(5);

        float index = (float)(v1_size + v2_size)/2;
        bool is_odd;
        if ((int)(index*10)%10 == 0) is_odd = false;
        else is_odd = true;
        if (is_odd){
            return merged_array[index];
        }
        else{
            return (float)(merged_array[index-1]+merged_array[index])/2;
        }
    }
};

[Github](https://github.com/henryleecode23/solve_record/blob/main/leetcode/4.%20Median%20of%20Two%20Sorted%20Arrays.cpp)
:::
[LeetCode](https://leetcode.com/problems/median-of-two-sorted-arrays/submissions/910943171/)

## 解釋
### 取得兩Vector長度

int v1_size = nums1.size(),
    v2_size = nums2.size();

使用Vector中的成員函式`size()`來獲取Vector長度
`v1_size`對應第一個`Vector`(nums1)的長度
`v2_size`對應第二個`Vector`(nums2)的長度

### 合併的同時排序

vector<int> merged_array;
int i=0, j=0;
while (i<v1_size and j<v2_size){
    if (nums1[i] < nums2[j]){
        merged_array.push_back(nums1[i++]);
    }
    else{
        merged_array.push_back(nums2[j++]);
    }
}

定義兩整數$i, j$作為兩Vector的指針
比較兩個Vector在當前指針所指向的數值並將較小的加入`merged_array`
在加入後更新該指針
(這裡使用後綴自增)
一直到有其中一個Vector的所有數字被比較完

### 加入剩下的數字

while (i<v1_size){
    merged_array.push_back(nums1[i++]);
}
while (j<v2_size){
    merged_array.push_back(nums2[j++]);
}

這裡乾脆的直接寫兩個`while`(主要是我懶得做判斷)
用來將還沒被放進`merged_vec`中的值放入

### 設定小數精準度

cout<<fixed<<setprecision(5);

可以注意到在範例測資1中的輸出值到了小數點後第5位
使用`setprecision`做設定

:::success
技巧: [小數精度](/_Og7VSUYTO2FkcXzhwRpSQ)
:::

### 計算中位數
中位數計算規則:
$$
\mathrm {Q} _{\frac {1}{2}}(x)={\begin{cases}x_{\frac {n}{2}},&{\mbox{if }}n{\mbox{ is odd number.}}\\{\frac {1}{2}}(x_{\lfloor\frac {n}{2}\rfloor}+x_{\lceil{\frac {n}{2}}\rceil}), &{\mbox{if }}n{\mbox{ is even number.}}\end{cases}}
$$
要注意的是因為索引值是從0開始算
所以當合併後的長度是偶數時, 索引值最大是一個奇數
同理當長度是奇數時, 索引值最大是偶數
|索引值|0|1|2|3|4|中位數|計算|
|-|-|-|-|-|-|-|-|
|數列1(長度是奇數)|1|2|3|4|5|3|`num[3-1]`|
|數列2(長度是偶數)|1|2|3|4||2.5|`(num[1]+num[2])/2`|

要判斷中位數的索引是奇偶數,需將原本`float`乘以10轉成`int`後再做判斷

float index = (float)(v1_size + v2_size)/2;
bool is_odd;
if ((int)(index*10)%10 == 0) is_odd = false;
else is_odd = true;

最後輸出

if (is_odd) return merged_array[index];
else return (float)(merged_array[index-1]+merged_array[index])/2;

## 心得
如果有實作過合併排序(merge sort)的話應該對合併的部分不陌生
再來是中位數計算跟數學上的中位數索引值不同 一個是從0一個從1
在思考上可能會有點打結

`Vector`熟練度+1

應該有不需要合併兩個`Vector`的做法 :thinking_face:

{%hackmd @henry-lee-code23/dark-theme %}