# 2024 「資訊科技產業專案設計」作業2

## 88 Merge Sorted Array

面試官：你好，今天我們會討論 LeetCode 的第88題「合併兩個有序數組」。你可以先簡單描述一下這道題的要求嗎？

面試者🧔：好的，這道題要求將兩個已經排序的數組合併成一個有序數組，並且結果需要儲存在 nums1 中。這在數據合併、排序等應用中經常會用到。題目給的條件是，nums1 有足夠的空間容納合併後的結果，但其中只有 m 個有效元素，而 nums2 中有 n 個元素。我們需要將 nums2 中的所有元素合併到 nums1 中，保持兩者的排序，並且不使用額外空間。

面試官：不錯，那你會如何著手解決這道題呢？

面試者🧔：我的解法是從兩個數組的末尾開始進行比較和合併，這樣可以避免覆蓋掉 nums1 中的有效數據。具體來說，我會用到三個指針變量：

i 指向 nums1 中最後一個有效元素的位置。
j 指向 nums2 中的最後一個元素。
k 指向 nums1 最後一個位置，這將是合併後放置結果的位置。

然後，我會從後往前比較 nums1[i] 和 nums2[j]，將較大的值放在 nums1[k]，並移動相應的指針。這樣可以確保在不覆蓋有效數據的前提下進行合併。

面試官：那能展示一下具體的程式碼嗎？

#include <stdio.h>

void merge(int* nums1, int m, int* nums2, int n) {
    int i = m - 1;  // 指向 nums1 的最後一個有效元素
    int j = n - 1;  // 指向 nums2 的最後一個元素
    int k = m + n - 1;  // 最終合併位置

    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }

    // 將剩餘的 nums2 元素拷貝到 nums1 中
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

面試官：很好，請解釋一下這段程式碼的邏輯吧。

面試者🧔：當然。在這裡，i 和 j 分別指向 nums1 和 nums2 的最後一個有效元素位置，k 是合併結果儲存的目標位置。接下來的流程是：

比較 nums1[i] 和 nums2[j] 的大小，將較大的元素放到 nums1[k]，然後向前移動指針 k。
重複這個過程直到其中一個數組被合併完。
如果 nums2 中還有剩餘元素，繼續將它們複製到 nums1 開頭，這樣可以確保最終結果有序。
這個方法能避免覆蓋 nums1 中的有效元素，同時實現從後往前合併的排序過程。

面試官：你對這段程式碼的時間和空間複雜度有什麼看法？

面試者🧔：這段程式碼的時間複雜度是 O(m + n)，因為需要遍歷 nums1 和 nums2 中的所有元素才能完成合併。在空間複雜度方面，這個方法是原地合併的，直接在 nums1 上操作，因此空間複雜度是 O(1)，沒有額外的空間需求。

面試官：很好，這是最優解嗎？還有其他可以優化的地方嗎？

面試者🧔：在這道題的條件下，這已經是最優解法。由於需要從後往前合併來避免覆蓋，所以在不使用額外空間的情況下，我認為這是最理想的方式。時間複雜度 O(m + n) 也是最小的，因為我們至少需要檢查所有元素。

面試官：很好的解釋。最後，你能總結一下這道題的關鍵點嗎？

面試者🧔：好的。這道題的關鍵在於利用數組已經排序的特性，從後往前合併，這樣可以避免覆蓋掉 nums1 中的有效數據。使用三個指針從末尾進行比較，確保 O(m + n) 的時間複雜度，並且保持 O(1) 的空間複雜度。

面試官：非常好，今天的表現很不錯，謝謝你！

面試者🧔：謝謝您的指導！